View abstract

Session I.3 - Graph Theory and Combinatorics

Monday, June 12, 17:30 ~ 18:00

New Ramsey Multiplicity Bounds and Search Heuristics

Olaf Parczyk

FU Berlin, Germany   -   This email address is being protected from spambots. You need JavaScript enabled to view it.

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 provide the fist substantial improvement on the 25-year-old upper bounds of Thomason on the Ramsey multiplicity of $K_4$ and $K_5$ and we settle the minimum number of independent sets of size $4$ in graphs with clique number at most $4$. Motivated by the elusiveness of the symmetric Ramsey multiplicity problem, we also introduce an 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 Sebastian Pokutta (ZIB Berlin and TU Berlin), Christoph Spiegel (ZIB Berlin) and Tibor Szabó (FU Berlin).

View abstract PDF