The ACO Seminar (2019–2020)

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–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 $\sqrt{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(\sqrt{n})$ or $\omega(\sqrt{n})$. This talk assumes no previous knowledge of graphons.

Before the talk, at 3:10pm, there will be tea and cookies in Wean 6220.