Source-linked AI summary
Recent developments in graph Ramsey theory
David Conlon, Jacob Fox, Benny Sudakov
TL;DR
Quantitative behaviour of graph Ramsey numbers remains poorly understood despite substantial progress. This survey synthesizes developments in classical Ramsey theory and its variants, including methods and open problems across complete, hypergraph, sparse, induced, and related settings. It highlights recent bounds and constructions while delimiting its coverage and noting unresolved questions.
Problem
The quantitative behaviour of Ramsey numbers remains poorly understood, including major gaps for complete 3-uniform hypergraphs and significant-factor improvements to established bounds.
Method
The paper surveys recent progress on classical Ramsey functions and variants, discussing results, proof methods, constructions, and related open problems.
Results
The survey records advances including triangle-free-process and semi-random proofs, stepping-up constructions, bounds for sparse graphs, and results on induced and regular induced subgraphs.
Takeaways & Limitations
Accurately determining r3(t) would yield accurate estimates for higher-uniformity Ramsey numbers, while degeneracy may provide a computable approximation for general graphs.
Takeaways & Limitations
The survey is not exhaustive and focuses mainly on asymptotic problems rather than exact Ramsey-number computation.
Abstract
from arXiv · showhide
Given a graph $H$, the Ramsey number $r(H)$ is the smallest natural number $N$ such that any two-colouring of the edges of $K_N$ contains a monochromatic copy of $H$. The existence of these numbers has been known since 1930 but their quantitative behaviour is still not well understood. Even so, there has been a great deal of recent progress on the study of Ramsey numbers and their variants, spurred on by the many advances across extremal combinatorics. In this survey, we will describe some of this progress.
1 Introduction
Ramsey theory studies guarantees that coloured or otherwise structured objects contain large organised substructures, with graph Ramsey theory as the survey’s focus. The section introduces classical, multicolour, hypergraph, and sparse-graph settings while emphasizing that key quantitative questions remain open.
- Ramsey theory asks when a structure must contain a large well-organised substructure, with examples across geometry, number theory, logic, and analysis.
- For any graph H, Ramsey’s theorem guarantees an N such that every two-colouring of K_N contains a monochromatic H; the least such N is r(H).
- The off-diagonal number r(s,t) is the least N forcing a red K_s or blue K_t, and Erdős–Szekeres supplied an early reasonable estimate whose improvement remains incomplete.
- For bounded-degree graphs with n vertices, the Ramsey number is at most c(∆)n, so this family has linear growth in its number of vertices.
- Ramsey’s theorem extends to q-colourings of k-uniform hypergraphs, but even complete 3-uniform hypergraphs have poorly understood Ramsey-number growth.
- The survey covers classical Ramsey functions and variants, mainly emphasizing asymptotic problems rather than exact computation, and is not exhaustive.
2 The classical problem
The survey presents major advances and persistent gaps in graph and hypergraph Ramsey theory, spanning complete graphs, sparse graphs, and higher-uniformity colourings. It highlights new bounds, probabilistic constructions, stepping-up methods, and connections to structural graph parameters.
- Complete graphs: r(t) = O(4^t) improves the diagonal Ramsey upper bound, but further substantial improvement remains a major open problem.The survey attributes the improvement to Thomason and notes that the best-known constants have changed only slightly over time.
- Complete hypergraphs: Stepping-up constructions generate lower bounds for uniformity k + 1 from bounds for uniformity k, effectively adding an exponential at each application.The survey illustrates the construction by encoding vertices as binary strings and colouring pairs according to the first differing coordinate.
- Complete hypergraphs: Theorem 2.9 establishes almost monochromatic subsets of order c√(log N) in every two-colouring of triples, matching the conjectured exponent.For fixed numbers of colours, such almost monochromatic subsets can be much larger than genuinely monochromatic subsets.
3 Variants
The survey considers selected variants of the usual Ramsey function, focusing on those the authors regard as most important.
- The section examines only a few of the many interesting variants of the usual Ramsey function.
3.1 Induced Ramsey numbers
Induced Ramsey numbers quantify how large a host graph must be to force induced monochromatic copies. Recent work gives near-exponential general bounds, polynomial bounds for bounded-degree targets, and strong pseudorandom-graph guarantees, while several extensions remain open.
- The induced Ramsey number rind(H) is the smallest order of a graph whose every two-edge-colouring contains an induced monochromatic copy of H.
- 2^{c n log n} bounds rind(H) for every n-vertex graph H, improving an earlier 2^{c n log^2 n} estimate.
- Explicit pseudorandom graphs can replace the earlier random projective-plane construction while achieving the same induced-Ramsey bounds.
- A sufficiently jumbled host graph forces every n-vertex graph to occur as an induced monochromatic copy, with all copies available in one colour.
- c n^{2∆+8} bounds the induced Ramsey number for every n-vertex graph of maximum degree ∆.
- The multicolour extension of the strongest general pseudorandom results remains open, as does an exponent independent of ∆ for bounded-degree targets.
3.2 Folkman numbers
Folkman numbers seek Ramsey behaviour in graphs that avoid a larger clique. Their bounds have improved substantially through random-graph methods, though the general scale remains conjectural.
- The Folkman number f(t) is the smallest order of a K_{t+1}-free graph whose every two-edge-colouring contains a monochromatic K_t.
- 786 is the current best stated upper bound for f(3).
- Random-graph Ramsey thresholds provided proofs of Folkman’s theorem and a framework for obtaining quantitative bounds.
- 2^{c t^4 log t} bounds f(t), improving earlier bounds through general methods for combinatorial theorems in random sets.
- The survey conjectures that Folkman numbers are at most exponential in t because current bounds lie close to the lower bound.
3.3 The Erd˝os–Hajnal conjecture
The Erdős–Hajnal conjecture predicts polynomial-sized cliques or independent sets in graphs excluding a fixed induced subgraph. The survey records broad partial results, special cases, stronger structural statements, and related open conjectures.
- The conjecture asks whether every induced-H-free n-vertex graph contains a clique or independent set of order at least n^{c(H)}.
- The conjecture holds for all graphs on at most four vertices and for the bull graph, but remains open for graphs including C5 and P5.
- The best general bound guarantees a clique or independent set of order e^{c(H)√log n} in every induced-H-free graph.
- Dependent random choice gives an off-diagonal result: if (log n1)(log n2) ≤ c(H) log n, an induced-H-free graph contains a clique of order n1 or an independent set of order n2.
- String graphs currently yield a clique or independent set of order n^{c/log log n}, while the full Erdős–Hajnal property remains open for them.
- Induced-H-free graphs contain complete bipartite graphs or independent sets with polynomial-sized parts, and also linear-sized subgraphs that are close to complete or empty.
- The survey proposes stronger structural conjectures for induced-H-free graphs, triangle-free graphs, coloured complete graphs, and 3-uniform hypergraphs.
3.4 Size Ramsey numbers
Size Ramsey numbers minimize the number of host edges rather than vertices, and related variants optimize other graph parameters or online exposure. Results range from linear bounds for paths to superlinear examples and major open problems.
- The size Ramsey number r̂(H) is the minimum number of edges in a graph that is Ramsey with respect to H.
- c n edges suffice for the size Ramsey number of the n-vertex path P_n.
- Graphs of maximum degree 3 can have superlinear size Ramsey numbers, disproving a linear bound for all bounded-degree graphs.
- The size Ramsey number of bounded-degree graphs is nevertheless subquadratic, while the conjectured lower-bound behaviour remains unresolved.
- The f-Ramsey framework minimizes an arbitrary graph parameter, including vertices, edges, chromatic number, or maximum degree.
- The degree-Ramsey question asks whether graphs of maximum degree ∆ can all be forced by hosts with bounded maximum degree depending only on ∆.
- For infinitely many t, the online Ramsey number is exponentially smaller than the size Ramsey number, although the ratio conjecture remains open.
3.5 Generalised Ramsey numbers
The survey studies generalized Ramsey functions that require colour diversity in every clique, highlighting progress, constructions, and persistent gaps in their quantitative behaviour.
- Definitions: The function f(n, p, q) is the minimum number of colours in an edge-colouring of K_n where every K_p receives at least q colours.For q = 2, this recovers the minimum colours needed to avoid monochromatic K_p.
- Erdős–Gyárfás function: Erdős and Gyárfás showed that f(n, p, p) is polynomial in n and asked whether q = p is the smallest polynomial regime.This left the subpolynomial behaviour of f(n, p, p − 1) open, even for p = 4.
- Erdős–Gyárfás function: For p = 4, Mubayi constructed a (4, 3)-colouring using at most e^{c√log n} colours, later extended to (5, 4)- and broader (p, 2⌈log p⌉−2)-colourings.The construction is based on coding vertices as elements of [m]^t and colouring pairs according to their first differing coordinate.
- Erdős–Gyárfás function: Conlon, Fox, Lee and Sudakov extended the construction to show that f(n, p, p − 1) is subpolynomial for every p ≥ 4.The authors explicitly expect the stated quantitative form to be far from best possible.
- Erdős–Rogers function: For the Erdős–Rogers function, the long-standing case t = s + 1 was resolved at order n^{1/2+o(1)}.The progression passed through an O(n^{2/3}) upper bound and matching lower-bound order up to logarithmic factors for f_{3,4}(n).
- Erdős–Rogers function: The methods also yield higher-uniformity lower bounds of (log^{(k−2)} n)^{1/3−o(1)} for f_s,s+1^(k)(n).These bounds improve an analogous result of Dudek and collaborators.
3.6 Monochromatic cliques with additional structure
This section studies monochromatic cliques subject to additional structure, including vertex weights and prescribed difference orders, and records sharp growth bounds alongside failures of natural extensions.
- Weighted cliques: Weighted Ramsey variants minimize the maximum weight of a monochromatic clique, with f(n) defined using w(S) = Σ_{i∈S} 1/log i.Erdős conjectured that this minimum tends to infinity.
- Weighted cliques: Rödl proved the conjecture with lower and upper bounds of order log log log log n.The upper-bound construction partitions [2,n] into rapidly growing intervals and controls clique sizes within each interval.
- Weighted cliques: A later result showed that Rödl’s upper bound is tight up to a constant factor, using interval decompositions, dependent random choice, and a weighted Ramsey theorem.The proof forces configurations resembling those in the upper-bound construction.
- Weighted cliques: For generalized weight functions, f(n, w_s) has order Θ(log^{(2s+1)} n).The section identifies this as part of the boundary separating convergent and divergent weighted Ramsey functions.
- Prescribed difference orders: For prescribed orders of consecutive differences, every q-colouring contains a monochromatic K_t once R = 2^{t^{20q}} vertices are available.Thus R(t;q) ≤ 2^{t^{20q}} for arbitrary permutations of [t−1].
- Prescribed difference orders: The natural hypergraph analogue fails: a three-uniform colouring forces consecutive differences in a monochromatic set to be monotone.This prevents realizing arbitrary prescribed difference orders in the hypergraph setting.
3.7 Ordered Ramsey numbers
Ordered Ramsey numbers can differ substantially from ordinary Ramsey numbers, although polynomial bounds hold for several structured graph classes and hypergraph paths exhibit a sharp contrast.
- Sparse ordered graphs: For ordered matchings M on n vertices, some orderings satisfy r_<(M) ≥ n^{c log n/log log n}, whereas ordinary matching Ramsey numbers are linear.The ordered lower bound holds for almost all orderings and is close to the general upper bound n⌈log n⌉.
- Structured ordered graphs: Bounded degeneracy and bounded interval chromatic number imply that r_<(H) is polynomial in the number of vertices.Interval chromatic number partitions the ordered vertices into independent intervals.
- Structured ordered graphs: Ordered graphs of bounded bandwidth also have polynomial ordered Ramsey numbers.For sufficiently large n relative to bandwidth ℓ, the theorem permits c_ℓ = O(ℓ), though this may not be optimal.
- Open problems: Determining whether every matching M satisfies r(K_3,M) = O(n^{2−ε}) for some ε > 0 remains open.Known lower bounds for suitable ordered matchings leave a substantial gap.
- Ordered hypergraphs: For k ≥ 3, the ordered Ramsey number of the monotone k-uniform tight path grows as a (k−2)-fold exponential in n, unlike the unordered number, which is linear.This is one of the strongest known separations between ordered and unordered Ramsey problems.
4 Concluding remarks
The concluding remarks emphasize open problems on large regular induced subgraphs and explicit Ramsey graphs, where probabilistic existence results substantially outpace known constructions.
- Regular induced subgraphs: The Erdős–Fajtlowicz–Staton conjecture asks whether every n-vertex graph contains a regular induced subgraph with ω(log n) vertices.Ramsey’s theorem guarantees only a regular induced subgraph of order at least 1/2 log n through a clique or independent set.
- Regular induced subgraphs: There are n-vertex graphs whose largest regular induced subgraph has order at most n^{1/2+ε}, and sharper examples exclude order cn^{1/2} log^{1/4} n.Any polynomial improvement on the latter upper bound would be significant.
- Explicit Ramsey graphs: Erdős’s probabilistic argument shows that almost all colourings avoid monochromatic K_t, but does not provide a constructive procedure for producing such a colouring.This motivates the problem of constructing explicit Ramsey graphs.
- Explicit Ramsey graphs: The Frankl–Wilson construction gives explicit graphs with no clique or independent set of order t, using vertices formed by fixed-size subsets and adjacency defined by intersection modulo a prime.The construction is a notable explicit example, although later work improved its bound without a simple description.
- Explicit Ramsey graphs: The survey notes that explicit constructions achieving r(t) > (1 + ε)^t remain unresolved.Erdős offered a $100 reward for any improvement of this kind.