List All Events

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.