Triangle Ramsey numbers of complete graphs

Basic Information

• Paper ID: 2312.06895
• Title: Triangle Ramsey numbers of complete graphs
• Authors: Jacob Fox (Stanford), Jonathan Tidor (Princeton), Shengtong Zhang (Stanford)
• Classification: math.CO (Combinatorics)
• Publication Date: arXiv:2312.06895v2 math.CO 1 Oct 2025
• Paper Link: https://arxiv.org/abs/2312.06895

Abstract

A graph $G$ is called $H$-Ramsey if every 2-coloring of its edges contains a monochromatic copy of $H$. The $F$-Ramsey number $r_F(H)$ of $H$ is defined as the minimum number of copies of $F$ in all $H$-Ramsey graphs. This generalizes the concepts of Ramsey numbers and size Ramsey numbers for graphs. In response to a question posed by Spiro, the authors prove that for sufficiently large $t$, $r_{K_3}(K_t)=\binom{r(K_t)}{3}$. The proof is based on a result in graph coloring: there exists an absolute constant $K$ such that every $r$-chromatic graph in which each edge is contained in at least $K$ triangles contains at least $\binom{r}{3}$ triangles in total.

Research Background and Motivation

Problem Background

1. Extension of Classical Ramsey Theory: Traditional Ramsey theory studies $r(H)$ (the minimum size of a complete graph such that any 2-coloring contains a monochromatic copy of $H$). This paper investigates the more general $F$-Ramsey number $r_F(H)$ (the minimum number of copies of $F$ in $H$-Ramsey graphs).
2. Known Results: Chvátal proved that $r_{K_2}(K_t) = \binom{r(K_t)}{2}$, meaning the complete graph $K_{r(K_t)}$ has the minimum number of edges among all $K_t$-Ramsey graphs.
3. Spiro's Conjecture: For all $s \leq t$, does $r_{K_s}(K_t) = \binom{r(K_t)}{s}$ hold?

Research Significance

• Theoretical Importance: This is the first study of $F$-Ramsey numbers for subgraphs $F$ other than vertices and edges
• Methodological Innovation: Deep integration of Ramsey theory with graph coloring theory
• Generalization Value: Analogous to Alon-Shikhelman's generalized Turán function $ex(n,F,H)$

Core Contributions

1. Main Theorem: Proves that for sufficiently large $t$, $r_{K_3}(K_t) = \binom{r(K_t)}{3}$ (Theorem 1.3)
2. Key Lemma: Establishes a connection between graph coloring and triangle counting (Theorem 1.5)
3. Technical Innovation: Develops coloring techniques for handling locally dense graphs
4. Methodological Contribution: Provides a framework for studying the general problem of $r_{K_s}(K_t)$

Methodology in Detail

Core Strategy

The proof consists of two main steps:

Step 1: Connection Between Ramsey Property and Chromatic Number (Proposition 1.4)

Key Observation:

• If $G$ is $K_t$-Ramsey, then $\chi(G) \geq r(K_t)$
• If $G$ is $K_t$-Ramsey critical, then every edge of $G$ is contained in some $K_t$

Proof Idea: By contradiction, assuming the existence of a $(r(K_t)-1)$-coloring allows construction of a 2-coloring of a $K_t$-Ramsey graph with no monochromatic $K_t$.

Step 2: Triangle Lower Bound for Locally Dense Graphs (Theorem 1.5)

Core Theorem: There exists an absolute constant $K$ such that every $r$-chromatic graph in which each edge is contained in at least $K$ triangles contains at least $\binom{r}{3}$ triangles.

Technical Framework

Fundamental Turán Argument (Section 2)

Theorem 2.2: For any $r$-chromatic graph $G$, $t(G) + \frac{1}{2}e(G) \geq \binom{r}{3} + \frac{1}{2}\binom{r}{2}$

Proof Techniques:

1. Construct a graph sequence $G \supseteq G_0 \supseteq G'_0 \supseteq G_1 \supseteq \cdots$
2. Each $G'_i$ is an $(r-i)$-critical subgraph, with $I_i$ being a maximum independent set in $G'_i$
3. Apply Turán's theorem to estimate the number of triangles containing each vertex

Coloring Theory Tools (Section 3)

1. Gallai's Theorem: Structure of small critical graphs
2. Vu's Theorem: Upper bounds on list chromatic number for locally sparse graphs
3. Harris's Theorem: Upper bounds on chromatic number based on triangle count
4. New Lemma 3.5: Improved coloring for degenerate locally sparse graphs

Main Proof Architecture

Handling Linear-Size Graphs (Section 4)

Lemma 4.1: For $r$-critical graphs with $O(r)$ vertices and clique number close to $r$, the number of triangles exceeds $\binom{r}{3}$

Proposition 4.2: For $r$-critical graphs with vertex count in the range $[2r-1, Cr]$, the number of triangles exceeds $\binom{r}{3}$

General Case Proof (Section 5)

Three cases are handled:

1. Small Clique Number Case: Application of Ramsey-Turán theorem
2. Large Clique Number Case: Application of the linear-size result above
3. Synthesis Argument: Weighted correction of independent set decomposition

Technical Innovations

1. Refinement of Turán Argument

• Rather than simply applying the classical Turán theorem, precise bounds are obtained through critical graph decomposition
• Introduction of "corrected weights" concept to handle cases containing large cliques

2. Localization to Globalization of Conditions

• Deriving global triangle lower bounds from the local condition "each edge is in $K$ triangles"
• Combining probabilistic methods with concentration inequalities (Azuma-Hoeffding, Talagrand inequalities)

3. Multi-Scale Analysis

• Different techniques for graphs of different sizes: Gallai's theorem (small graphs), Ramsey-Turán (medium graphs), probabilistic coloring (large graphs)

Experimental Setup

This is a purely theoretical paper with no experimental verification. All results are obtained through mathematical proof.

Main Results

Core Theorem

Theorem 1.3: For sufficiently large $t$, $r_{K_3}(K_t) = \binom{r(K_t)}{3}$

Supporting Results

1. Theorem 1.5: Triangle lower bound for locally dense graphs
2. Theorem 2.2: Improved Turán-type inequality
3. Lemma 3.5: Improved coloring for degenerate graphs

Asymptotic Results

Corollary 2.3: $r_{K_3}(K_t) \geq (1-o(1))\binom{r(K_t)}{3}$

Related Work

Classical Results

• Chvátal's Theorem: $r_{K_2}(K_t) = \binom{r(K_t)}{2}$
• Ramsey Theory: Classical studies of $r(K_t)$
• Size Ramsey Numbers: Related work on $\hat{r}(H)$

Modern Developments

• Generalized Turán Problems: Alon-Shikhelman's $ex(n,F,H)$
• Hypergraph Size Ramsey Numbers: Work by McKay and others
• Probabilistic Methods: Rödl-Ruciński threshold functions

Technical Tools

• Graph Coloring Theory: Molloy-Reed's coloring of locally sparse graphs
• Ramsey-Turán Theory: Erdős-Sós theorem
• Probabilistic Concentration: Applications of modern concentration inequalities

Conclusions and Discussion

Main Conclusions

1. Confirms the correctness of Spiro's conjecture for the case $s=3$ with sufficiently large $t$
2. Establishes new connections between Ramsey theory and graph coloring theory
3. Develops new techniques for handling locally dense graphs

Limitations

1. Finiteness Restriction: Only holds for "sufficiently large $t$"; small $t$ cases remain unresolved
2. Special Cases: Only resolves the case $s=3$; the general case remains open
3. Constant Dependence: The constant $K$ in the proof may be large, limiting practical applications

Future Directions

1. Complete Conjecture: Prove the general $r_{K_s}(K_t) = \binom{r(K_t)}{s}$
2. Finite Cases: Handle small values of $t$
3. Other Graph Pairs: Study cases where $(F,H)$ are not complete graphs
4. Computational Complexity: Analyze the computational complexity of computing $r_F(H)$

In-Depth Evaluation

Strengths

1. Theoretical Depth: Skillfully combines multiple mathematical branches (Ramsey theory, graph coloring, probabilistic methods)
2. Technical Innovation: Develops new methods for handling locally dense conditions
3. Clear Structure: Proof proceeds in layers with rigorous logic
4. Generality: Establishes foundations for studying broader $F$-Ramsey numbers

Technical Highlights

1. Weight Correction Technique: Introduction of corrected weights in independent set selection to handle large cliques
2. Multi-Scale Analysis: Employs the most suitable techniques for graphs of different sizes
3. Probabilistic Coloring: Skillfully applies probabilistic methods to deterministic problems

Shortcomings

1. Non-Constructive: The proof is existential and does not provide explicit construction of extremal graphs
2. Constant Estimation: Involved constants may be large, limiting practical significance
3. Technical Complexity: The proof relies on multiple deep results, raising the barrier to understanding

Impact Assessment

1. Theoretical Contribution: Establishes important foundations for $F$-Ramsey number theory
2. Methodological Value: The technical framework may be applicable to other combinatorial problems
3. Follow-Up Research: Paves the way for resolving the complete Spiro conjecture

Applicable Scenarios

1. Theoretical Research: Combinatorics and extremal graph theory
2. Method Borrowing: Analysis of similar local-to-global problems
3. Educational Value: Demonstrates comprehensive technical application in modern combinatorics

References

The paper cites 23 important references, covering:

• Classical Ramsey theory (Erdős et al.)
• Modern graph coloring theory (Alon-Krivelevich-Sudakov, Molloy-Reed)
• Probabilistic methods (concentration inequality literature)
• Generalized Turán problems (Alon-Shikhelman et al.)

Overall Assessment: This is a high-quality theoretical paper that achieves important progress in the classical field of Ramsey theory. Although it resolves only a special case of the general conjecture, the techniques and ideas developed provide important tools for further advancement in the field. The paper demonstrates outstanding technical depth and innovation, representing a significant contribution to combinatorics.