New Ramsey multiplicity bounds and search heuristics

Abstract

We study two related problems concerning the number of monochromatic cliques in two-colorings of the complete graph that go back to questions of Erdős. Most notably, we “significantly” improve the best known upper bounds on the Ramsey multiplicity of K_4 and K_5 and settle the minimum number of independent sets of size four in graphs with clique number at most four. Motivated by the elusiveness of the symmetric Ramsey multiplicity problem, we also introduce the off-diagonal variant and obtain tight results when counting monochromatic K_4 or K_5 in only one of the colors and triangles in the other. The extremal constructions for each problem turn out to be blow-ups of a finite graph and were found through search heuristics. They are complemented by lower bounds and stability results established using flag algebras, resulting in a fully computer-assisted approach. More broadly, these problems lead us to the study of the region of possible pairs of clique and independent set densities that can be realized as the limit of some sequence of graphs. Joint work with Olaf Parczyk, Sebastian Pokutta, and Christoph Spiegel.

Speaker Intro

Tibor Szabó is Professor of Mathematics at the Freie Universität Berlin. He obtained his PhD at The Ohio State University in 1996. Before joining FU Berlin in 2009 he was a member at the Institute for Advanced Study in Princeton, J.L.Doob Research Assistant Professor at the University of Illinois at Urbana-Champaign, senior researcher at the ETH Zurich, and Associate Professor at McGill University. His research focuses on combinatorics and graph theory, their probabilistic, algebraic, and topological connections, as well as their applications in computer science.