Spiegel, Christoph
Refine
Document Type
- In Proceedings (8)
- Article (5)
Language
- English (13)
Has Fulltext
- no (13)
Is part of the Bibliography
- no (13)
Institute
Sparse Model Soups
(2024)
The Hales-Jewett Theorem states that any r-colouring of [m]ⁿ contains a monochromatic combinatorial line if n is large enough. Shelah's proof of the theorem implies that for m = 3 there always exists a monochromatic combinatorial line whose set of active coordinates is the union of at most r intervals. For odd r, Conlon and Kamčev constructed r–colourings for which it cannot be fewer than r intervals. However, we show that for even r and large n, any r–colouring of [3]ⁿ contains a monochromatic combinatorial line whose set of active coordinates is the union of at most r−1 intervals. This is optimal and extends a result of Leader and Räty for r=2.
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 the complete graph on 4 vertices 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.