Seminars & Colloquia Calendar

Download as iCal file

Discrete Math

Super-logarithmic cliques in dense inhomogeneous random graphs

Gwen Mckinley (MIT)

Location:  Hill 705
Date & time: Monday, 11 November 2019 at 2:00PM - 3:00PM

Abstract: In the theory of dense graph limits, a graphon is a symmetric measurable function W from [0,1]^2 to [0,1]. Each graphon gives rise naturally to a random graph distribution, denoted G(n,W), that can be viewed as a generalization of the Erdos-Renyi random graph. Recently, Dolezal, Hladky, and Mathe gave an asymptotic formula of order log(n) for the size of the largest clique in G(n,W) when W is bounded away from 0 and 1. We show that if W is allowed to approach 1 at a finite number of points, and displays a moderate rate of growth near these points, then the clique number of G(n,W) will be of order ?n almost surely. We also give a family of examples with clique number of order n^c for any c in (0,1), and some conditions under which the clique number of G(n,W) will be o(?n) or omega(?n). This talk assumes no previous knowledge of graphons.

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.