Fully Computer-Assisted Proofs in Extremal Combinatorics

We present a fully computer-assisted proof system for solving a particular family of problems in Extremal Combinatorics. Existing techniques using Flag Algebras have proven powerful in the past, but have so far lacked a computational counterpart to derive matching constructive bounds. We demonstrate that common search heuristics are capable of finding constructions far beyond the reach of human intuition. Additionally, the most obvious downside of such heuristics, namely a missing guarantee of global optimality, can often be fully eliminated in this case through lower bounds and stability results coming from the Flag Algebra approach. To illustrate the potential of this approach, we study two related and well-known problems in Extremal Graph Theory that go back to questions of Erdős from the 60s. Most notably, we present the first major improvement in the upper bound of the Ramsey multiplicity of K_4 in 25 years, precisely determine the first off-diagonal Ramsey multiplicity number, and settle the minimum number of independent sets of size four in graphs with clique number strictly less than five.

Authors

• Olaf Parczyk Freie Universität Berlin
• Sebastian Pokutta Zuse Institute Berlin Technische Universit ̈at Berlin
• Christoph Spiegel Zuse Institute Berlin
• Tibor Szabó Freie Universität Berlin

Keywords

• ML: Optimization
• SO: Heuristic Search
• SO: Local Search
• SO: Metareasoning and Metaheuristics