# Colloquium by Gweneth Anne McKinley (MIT, Cambridge, USA): Super-logarithmic cliques in dense inhomogeneous random graphs

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 Erdös-Rényi 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 ω(√*n*). This talk assumes no previous knowledge of graphons.

### Time & Location

Jan 27, 2020 | 04:00 PM s.t.

Freie Universität Berlin

Institut für Informatik

Takustr. 9

14195 Berlin

Room 005 (Ground Floor)