Combinatorics and Probability Seminar
Gweneth McKinley
MIT
Super-logarithmic cliques in dense inhomogeneous random graphs
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 $\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.
Monday October 28, 2019 at 3:00 PM in 612 SEO