Abstract
Extremal Combinatorics is one of the most active topics in Discrete Mathematics, dealing with problems often motivated by questions in Theoretical Computer Science, Geometry, and Game Theory. This paper presents a collection of problems and results in the area, including solutions or partial solutions to open problems suggested by various researchers. The topics considered include Extremal Graph Theory, Combinatorial Geometry, and Combinatorial Number Theory. As a sequel to two previous works, this collection highlights various extremal problems that demonstrate the power of modern combinatorial techniques.
Introduction
Extremal combinatorics investigates the maximum or minimum possible size of a collection of mathematical objects satisfying certain properties. In this third installment of his series on the subject, Noga Alon tackles a diverse array of "combinatorial gems." By leveraging a toolkit that spans the probabilistic method, algebraic graph theory, and combinatorial designs, Alon settles several long-standing conjectures and provides significantly tighter bounds for fundamental problems across graph theory, geometry, and combinatorial number theory.
Hamilton Cycles in Regular Tournaments
A tournament is a directed graph formed by orienting every edge of a complete undirected graph. A "regular" tournament is one where every vertex has the same in-degree and out-degree—essentially a scenario where every player in a round-robin competition wins exactly half their matches.
A long-standing question posed by Thomassen in 1990 asked whether there exist regular tournaments containing as many directed Hamilton cycles as a random tournament. Alon confirms this in Theorem 1.1, proving that for $n \equiv 1, 3 \pmod 6$, there exists a regular tournament with more than $(n-1)!/2^n$ Hamilton cycles. This result bridges the gap between structured regular tournaments and the probabilistic behavior of random graphs.
Advancements in Homometric Sets
In any connected graph, two disjoint sets of vertices are considered "homometric" if the multisets of their pairwise distances are identical. The challenge lies in determining how large these sets can be guaranteed to be relative to the total number of vertices $n$.
Previous research established a lower bound that was merely logarithmic ($\log n / \log \log n$). Alon provides a significant "quadratic" boost to this bound in Theorem 2.1, demonstrating that homometric sets must be at least as large as $\Omega((\log n)^2 / (\log \log n)^2)$. While this remains distant from the known upper bound of $n/4$, it represents a substantial step forward in understanding the distance profiles of graph subsets.
Disproving Uniformity in Steiner Triple Systems
Steiner Triple Systems (STS) are highly symmetric set systems where every pair of elements is contained in exactly one triple. A conjecture by Goldberg, Rajendraprasad, and Mathew suggested that all STSs of the same size share the same "domination number" (the size of the smallest set of vertices that hits every triple).
Alon disproves this conjecture (Theorem 3.2) by showing that for large systems, the domination numbers can diverge wildly. He constructs examples where one system has a domination number linear in size, while another is significantly smaller, proving that the structural symmetry of an STS does not enforce uniformity in its extremal properties.
The Running Intersection Property and Matrix Covers
The paper also makes significant contributions to the intersection of combinatorics and computer science:
- Algorithmic RIP: The Running Intersection Property (RIP) is a structural constraint used in database theory and statistics. Alon proves Spiegler’s conjecture, showing that a simple "expansive" greedy ordering is sufficient to determine if a family of sets satisfies RIP. This transforms a complex structural verification into an efficient algorithmic check.
- Matrix Cover Numbers: In the study of sign matrices, Alon investigates the $\epsilon$-cover number—the minimum number of rows needed to "represent" all other rows within a certain error margin. Linking this to the Vapnik-Chervonenkis (VC) dimension, Alon shows that for matrices with VC-dimension 1, existing upper bounds are essentially optimal.
Methodological Toolkit
The results in this paper are achieved through a "greatest hits" of combinatorial methods:
- The Probabilistic Method: Utilizing linearity of expectation and the Lovász Local Lemma to prove the existence of structures without explicit construction.
- Combinatorial Designs: Using STSs as building blocks for counterexamples.
- Algebraic Tools: Applying the properties of Totally Unimodular (TU) matrices to bound cover numbers.
- Graph Algorithms: Employing Depth First Search (DFS) and Breadth First Search (BFS) in novel ways to establish the existence of long paths and large homometric sets.
Conclusion and Future Work
While "Problems and Results in Extremal Combinatorics – III" settles several questions, it opens new avenues for research. The gap in homometric set bounds remains a major challenge, and the behavior of matrix cover numbers for VC-dimensions greater than 1 appears significantly more complex. Alon’s work continues to demonstrate that extremal combinatorics is not just a collection of isolated puzzles, but a deeply interconnected field with profound implications for theoretical computer science and beyond.
Summary updated