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.