Independence in random graph models

Various random graphs models satisfy that each edge appears independently of all other edges but those in a bounded degree graph. Examples include Erdös–Renyi random graphs, random Cayley graphs, random Latin square graphs, and random entangled graphs. We begin the systematic study of random graphs under this weak independence hypothesis, focusing on the clique number. We prove that for $0<p<1$ fixed, for any such $N$-vertex random graph with edge probabilities each $p$, the clique number is asymptotically almost surely at least $(2-o(1))\log_{1/p} N$ and at most $O(\log N \log \log N)$. The lower bound is tight for the Erdös–Renyi random graph, and the upper bound is tight for random Cayley graphs in finite vector spaces over a fixed finite field. The upper bound solves various open problems in the area.

This is based on joint work with David Conlon, Huy Tuan Pham, and Liana Yepremyan.