Computer Science/Discrete Mathematics Seminar I

A beautiful conjecture of Erd\H{o}s-Simonovits and Sidorenko states that if $H$ is a bipartite graph, then the random graph with edge density $p$ has in expectation asymptotically the minimum number of copies of $H$ over all graphs of the same order and edge density. This conjecture also has an equivalent analytic form and has connections to a broad range of topics, such as matrix theory, Markov chains, graph limits, and quasirandomness. In this talk we prove this conjecture for any $H$, which has a vertex complete to the other part, and deduce an approximate version of Sidorenko's conjecture for all $H$. The proof uses a simple and yet surprisingly powerful probabilistic technique which shows how to find in a dense graph a large subset of vertices in which all (or almost all) small subsets have many common neighbors. Recently this technique has had several striking applications to Extremal Graph Theory, Ramsey Theory, Additive Combinatorics, and Combinatorial Geometry. Joint work with D. Conlon and J. Fox