Tough Ramsey Graphs Without Short Cycles

Noga AlonJournal of Algebraic Combinatorics 1995 · DOI

TL;DR

Noga Alon uses spectral graph theory and error-correcting codes to explicitly construct graphs that are simultaneously "tough" (hard to disconnect) and have high girth (no short cycles). This work disproves a long-standing conjecture by Chvátal regarding pancyclic graphs and provides a significantly improved explicit lower bound for the Ramsey number $R(3, m)$.

What Problem Does This Paper Address?

In graph theory, toughness is a measure of a graph's resilience. A graph is $t$-tough if, to break it into $x$ connected components, you must remove at least $tx$ vertices. Intuitively, tough graphs are highly interconnected.

For decades, mathematicians explored the relationship between toughness and other properties like Hamiltonicity (having a cycle that visits every vertex) and pancyclicity (containing cycles of every possible length from 3 to $n$). A conjecture by Václav Chvátal suggested that if a graph is "tough enough" (exceeding some constant $t_0$), it must be pancyclic.

Additionally, the paper tackles a classic problem in Ramsey theory: constructing triangle-free graphs with a small independence number $m$ (the largest set of vertices with no edges between them). Finding the maximum number of vertices $R(3, m)$ such a graph can have is a fundamental challenge in combinatorics.

Methods

Alon moves away from the probabilistic "random graph" methods common in the field, opting instead for explicit algebraic constructions. The two primary tools are:

  1. Spectral Graph Theory: The author leverages the relationship between a graph's "spectral gap"—the difference between its largest eigenvalue ($d$) and the absolute value of its other eigenvalues ($\lambda$). He proves that $(n, d, \lambda)$-graphs with a large gap are inherently tough.
  2. Coding Theory (BCH Codes): To address the Ramsey number problem, Alon constructs "code graphs." Vertices are represented as binary vectors, and edges are defined based on the properties of Bose-Chaudhuri-Hocquenghem (BCH) codes. Specifically, he uses the parity-check matrix of a dual BCH code to ensure the graph is triangle-free while maintaining a small independence number.

Datasets

Not discussed in the paper. As a theoretical mathematics paper, it relies on formal proofs and algebraic constructions rather than empirical datasets.

Key Insights and Ideas

  • The Spectral-Toughness Connection: The most significant theoretical insight is Proposition 2.1, which provides a lower bound for toughness based on eigenvalues. It shows that any regular graph where the second-largest eigenvalue is small relative to the degree is guaranteed to be tough. This allows the author to use well-known "expander" graphs (like Ramanujan graphs) to solve toughness problems.
  • High Girth vs. Pancyclicity: By proving that $t$-tough graphs can have arbitrarily high girth (the length of the shortest cycle), Alon effectively kills Chvátal’s pancyclicity conjecture. If a graph has a girth of 10, it cannot contain cycles of length 3, 4, or 5, and thus cannot be pancyclic, no matter how tough it is.
  • Algebraic Ramsey Bounds: Alon demonstrates that the structure of error-correcting codes is perfectly suited for building Ramsey graphs. The "triangle-free" property of the graph corresponds directly to the "minimum distance" properties of the underlying BCH code.

Key Results

  • Theorem 1.2: For every toughness value $t$ and every girth $g$, there exists an explicit $t$-tough graph with girth greater than $g$. This strengthens previous results that only covered the triangle-free ($g=3$) case.
  • Ramsey Number Improvement: The paper provides an explicit construction of triangle-free graphs with independence number $m$ on $\Omega(m^{4/3})$ vertices. At the time of publication, this was a significant improvement over previous explicit constructions by Erdős and others.
  • Toughness Scaling: The author proves that for any girth $g$, there are infinitely many graphs where toughness grows as a power of the number of vertices ($n^{c/g}$).

Limitations and Future Work

  • Non-Optimized Constants: The author notes that he made no attempt to optimize the constant factors in the toughness propositions, leaving room for tighter bounds.
  • The $n(t, g)$ Problem: Determining the smallest possible number of vertices $n$ required to achieve a specific toughness $t$ and girth $g$ remains an open and difficult problem.
  • Further Ramsey Improvements: In a "Note added in Proof," Alon mentions he discovered an even better construction using "orthonormal labelings" that pushes the Ramsey bound to $\Omega(m^{3/2})$, suggesting the BCH code approach was just the beginning of a more powerful technique.

Summary updated

BibTeX
@article{alon1995tough,
  author = {Noga Alon},
  title = {{Tough Ramsey Graphs Without Short Cycles}},
  journal = {Journal of Algebraic Combinatorics},
  year = {1995},
  doi = {10.1023/a:1022453926717},
}
Figure