Independence in random graphs

Zoom Link

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–Rényi 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 loglog N). The lower bound is tight for the Erdős–Rényi 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. We will also discuss the solution of conjectures of Ruzsa on quantitative versions of Freiman's theorem and of Alon and Orlitsky in information theory building on the same methods. Based on joint works with David Conlon, Huy Tuan Pham, and Liana Yepremyan.

Please report video problems to itsupport@slmath.org.

See more of our Streaming videos on our main VMath Videos page.