A note on regular Ramsey graphs

Noga Alon, Sonny Ben-Shimon, Michael KrivelevichJ. Graph Theory 2010 · DOI

Abstract

In extremal combinatorics, the Ramsey number $R(3, t)$ denotes the maximum number of vertices in a triangle-free graph with independence number less than $t$. While the asymptotic behavior of $R(3, t)$ is well-established, the specific properties of regular Ramsey graphs remained a point of inquiry. This note, based on the work of Noga Alon, Sonny Ben-Shimon, and Michael Krivelevich, demonstrates that the regularity constraint does not alter the asymptotic bounds of triangle-free Ramsey graphs. By employing a construction involving the triangle-free process, the Hajnal-Szemerédi Theorem, and the Gale-Ryser Theorem, the authors prove that $R^{reg}(3, t) = \Theta(t^2 / \log t)$.

Introduction

The study of Ramsey numbers is a cornerstone of graph theory, focusing on the emergence of order within large discrete structures. Specifically, the Ramsey number $R(3, t)$ represents the smallest integer $n$ such that every graph on $n$ vertices contains either a triangle ($K_3$) or an independent set of size $t$. In 1995, Jeong Han Kim established the asymptotic behavior of this value as $\Theta(t^2 / \log t)$. Subsequent work by Tom Bohman provided a more intuitive understanding of this bound through the "triangle-free process," a stochastic algorithm that generates triangle-free graphs with small independence numbers.

However, a specific structural question persisted: does the requirement of regularity—where every vertex possesses the same degree—impact these extremal bounds? While many graphs produced by randomized processes are "almost" regular, proving the existence of perfectly regular graphs with optimal Ramsey properties requires a more sophisticated constructive approach.

The Regularity Problem

A graph is $d$-regular if every vertex has degree $d$. In the context of Ramsey theory, regular graphs are often more difficult to construct than general graphs because the degree constraint limits the flexibility of edge placement. The central challenge addressed by Alon, Ben-Shimon, and Krivelevich is whether the independence number $\alpha(G)$ of a regular triangle-free graph $G$ can be kept as small as that of a non-regular one without violating the triangle-free condition.

Methodology: The Bipartite Patching Technique

The authors propose a "gadget-like" construction to transform an almost-regular triangle-free graph into a perfectly regular one without introducing triangles or significantly increasing the independence number.

1. Initial Graph Generation

The process begins with the $K_3$-free process analyzed by Bohman. This randomized algorithm yields a graph $G$ that is triangle-free and has an independence number $\alpha(G) \le C\sqrt{n \log n}$. Crucially, this graph is "almost" regular, meaning the variance in vertex degrees is relatively small.

2. Equitable Partitioning

To manage the degree discrepancies, the authors utilize two copies of the generated graph. They apply the Hajnal-Szemerédi Theorem, which guarantees that the vertices of these graphs can be partitioned into independent sets (color classes) of nearly equal size. This partitioning provides a structured framework for adding edges.

3. The Gale-Ryser Transformation

The core of the construction lies in the application of the Gale-Ryser Theorem. This theorem defines the necessary and sufficient conditions under which a bipartite graph can be constructed with a specific degree sequence. By treating the degree deficits of the vertices as the target degree sequence for a bipartite graph, the authors add edges between the independent sets of the two graph copies.

Because these new edges are added only between sets that are already independent, and because the connection is bipartite, no new triangles can be formed. This "smoothing" process effectively fills in the missing degrees for every vertex, resulting in a perfectly regular graph.

Key Results

The primary contribution of this work is the formal proof of the existence of regular Ramsey graphs that match the efficiency of general Ramsey graphs.

Theorem 1.1: There exists a positive constant $C$ such that for every $n$, there is a regular triangle-free graph $G$ on $n$ vertices with independence number $\alpha(G) \le C\sqrt{n \log n}$.

This result implies that the regular Ramsey number $R^{reg}(3, t)$ is asymptotically equivalent to the standard Ramsey number: $$R^{reg}(3, t) = \Theta(R(3, t)) = \Theta\left(\frac{t^2}{\log t}\right)$$

In essence, the constraint of regularity is "asymptotically free"—it does not require a significant increase in the number of vertices to maintain the same Ramsey properties.

Discussion and Future Directions

The findings reinforce the robustness of the triangle-free process and suggest that regularity is a natural property that can be imposed on many extremal structures. However, the current proof is specific to the $k=3$ (triangle-free) case.

The authors propose Conjecture 3.1, suggesting that for every $k \ge 2$, there exists a constant $c_k$ such that $R^{reg}(k, \ell) \ge c_k R(k, \ell)$ for all $\ell \ge 2$. While recent advancements in $H$-free processes by Bohman and Keevash provide a potential path forward, the lack of precise asymptotic values for $R(k, \ell)$ when $k > 3$ remains a significant hurdle for a generalized proof.

Conclusion

By bridging the gap between almost-regular and perfectly regular graphs, Alon, Ben-Shimon, and Krivelevich have provided a definitive answer for the $R(3, t)$ case. Their bipartite patching technique offers a versatile tool for degree regularization in extremal graph theory, confirming that the most efficient Ramsey graphs can indeed be regular.

Summary updated

BibTeX
@article{alon2010note,
  author = {Noga Alon and Sonny Ben-Shimon and Michael Krivelevich},
  title = {{A note on regular Ramsey graphs}},
  journal = {J. Graph Theory},
  year = {2010},
  doi = {10.1002/jgt.20453},
}
Figure