Recent developments in graph Ramsey theory

• For every graph H, Ramsey’s theorem [174] guarantees an N such that every two-colouring of K_N contains a monochromatic H; the least such N is r(H).Source: §1 · p. 1
• Erdős and Szekeres gave the first reasonable off-diagonal estimates; efforts to sharpen them remain only partly successful, and these problems influenced random graphs, probabilistic methods, and quasirandomness.Source: §1 · p. 2
• For an n-vertex graph H of maximum degree ∆, Chvátal, Rödl, Szemerédi and Trotter proved r(H) ≤ c(∆)n, with c depending only on ∆.Source: §1 · p. 2
• Ramsey’s theorem extends to q-colourings of k-uniform hypergraphs, with the least N guaranteeing a copy of some H_i in colour i denoted r_k(H_1, . . . , H_q).Source: §1 · p. 2
• Even for complete 3-uniform hypergraphs, r3(t)’s growth is poorly understood; an accurate estimate for r3(t) would imply accurate estimates for all rk(t), k ≥ 4.Source: §1 · p. 2
• The survey covers classical Ramsey functions and variants, but is not exhaustive and mainly treats asymptotic questions rather than exact Ramsey-number computations.Variants discussed include induced, size, and ordered Ramsey numbers.Source: §1 · p. 3

2.1 Complete graphs

• Thomason improved the diagonal Ramsey upper bound, and Conlon later gave a superpolynomial improvement on the Erdős–Szekeres bound.Conlon’s proof uses the p = 1 and p = 2 cases of Observation 2.1 to derive quasirandomness, then a counting argument to obtain a contradiction.Source: §2.1 · p. 4
• Spencer improved Erdős’ diagonal lower bound by a factor of two, while the best general off-diagonal lower bound is due to Bohman and Keevash.Even for s = 4, the upper and lower bounds still differ polynomially.Source: §2.1 · pp. 5–6
• Kim showed that the off-diagonal upper bound for r(3, t) is sharp up to a constant; Bohman reproved the lower bound using the triangle-free process.The process adds edges while avoiding triangles, and its independence number yields the lower bound; Bohman and Keevash and Fiz Pontiveros, Griffiths and Morris later refined its running-time estimates.Source: §2.1 · p. 5

2.2 Complete hypergraphs

• For hypergraph Ramsey numbers, Erdős, Hajnal and Rado established a lower bound for r3(t), while the upper and lower bounds remain separated by an exponential.The stepping-up lemma of Erdős and Hajnal gains an exponential at each increase in uniformity, so a double-exponential lower bound for r3(t) would close the gap for all uniformities.Source: §2.2 · p. 7
• For three colours, the authors improved the lower bound for r3(t; 3), strengthening evidence that it grows as a double exponential.Their bound improves on the earlier result of Erdős and Hajnal.Source: §2.2 · p. 8
• For every ǫ > 0, every two-colouring of triples has a subset of order c√(log N) whose triples are at least 1 − ǫ one colour.For k-tuples and q colours, a related result gives subsets of order (log N)^δ with δ depending on ǫ; whether δ can be 1/(k − 1) for k ≥ 4 remains open.Source: §2.2 · p. 9
• For r3(4,t), the lower bound 2^(c′t log t) complements the upper bound 2^(ct^2 log t), while Erdős and Hajnal’s conjecture is that log r3(4,t)/t tends to infinity.The lower-bound construction colours tournament triples red when they form cyclic triangles and blue otherwise.Source: §2.2 · p. 10

2.3 Sparse graphs

• For bounded-degree bipartite graphs, r(H) ≤ 2^(cΔ)n; for general bounded-degree graphs, the authors improve the linear bound to c(Δ) ≤ 2^(cΔ log Δ).The general-graph proof uses a more symmetric embedding strategy that splits H into two lower-degree parts.Source: §2.3 · pp. 12–13
• For hypercubes, the best stated upper bound is r(Qn) = O(2^(2n)), quadratic in the number of vertices, whereas Burr and Erdős conjectured a linear bound.The section also conjectures r(H) ≤ 2^(O(d))n for d-degenerate n-vertex graphs; a result of Fox and Sudakov establishes this up to a factor of log^2 d(H).Source: §2.3 · pp. 13–14
• Every p-arrangeable graph has Ramsey number at most c(p)n; this includes planar graphs, graphs embeddable on a fixed surface, and almost surely G(n,d/n) for fixed d [37, 185, 117].For the random graph, the cited result gives arrangeability on the order of d^2.Source: §2.3 · p. 14
• For bounded-degree k-uniform hypergraphs, the section reports linear Ramsey bounds, while a 1-degenerate 4-uniform example has Ramsey number at least 2^Ω(n^(1/3)) [66, 163, 67, 148].The earlier regularity-based proof gives an Ackermann-type bound; a later proof uses a hypergraph generalization of dependent random choice.Source: §2.3 · p. 15

2.4 Graphs with a given number of edges

• For any graph H with m edges and no isolated vertices, Sudakov’s theorem gives r(H) ≤ 2^(c√m).For graphs of degeneracy at most d, the section also gives a bound exponential in m when d is at most 10m/n.Source: §2.4 · pp. 15–16
• For 3-uniform hypergraphs with m edges and no isolated vertices, a 4-colour example has Ramsey number at least 2^(2^(c′√m)), while the general upper bound is 2^(2^(c√(m log m))) [54].For uniformity k ≥ 4, the section gives the upper bound t_k(c_(k,q)m), with t_1(x)=x and t_(i+1)(x)=2^t_i(x), for q colours [54].Source: §2.4 · p. 16

2.5 Ramsey goodness

• The Chvátal–Harary construction gives r(G,H) ≥ (|G|−1)(χ(H)−1)+1 for connected G; when |G| ≥ σ(H), Burr’s refinement adds a red clique of order σ(H)−1.Here σ(H) is the smallest colour-class size among χ(H)-colourings of H’s vertices.Source: §2.5 · pp. 16–17
• Trees are s-good for every s, but trees are not H-good for every graph H, and good expanders are not 3-good.Brandt’s result implies that, for sufficiently large Δ, almost every sufficiently large Δ-regular graph is not 3-good.Source: §2.5 · p. 17
• Connected graphs with maximum degree Δ and bandwidth at most cn are H-good for every fixed H, for some c > 0 depending on Δ and H.The result allows bandwidth to grow linearly with the order of the graph.Source: §2.5 · p. 17
• Connected d-degenerate graphs with sufficiently small separators are s-good, and connected graphs excluding any fixed minor are s-good for every s ≥3.The separator result applies for s ≥3 and a separator of size |V(G)|^(1−γ), with parameters as in Theorem 2.24; it implies the corresponding result for connected planar graphs.Source: §2.5 · pp. 17–18
• The family of hypercubes is s-good for every s ≥3, resolving an outstanding question about their Ramsey numbers.For Q_n, this asks whether r(Q_n, K_s) = (s −1)(2^n −1) + 1 for sufficiently large n.Source: §2.5 · p. 18

2.6 Ramsey multiplicity

• The 5-wheel is common, despite K4 and every graph containing K4 being non-common [211, 139].The 5-wheel is the smallest 4-chromatic graph without a K4; its commonness was established using flag algebras.Source: §2.6 · p. 19
• For bipartite graphs, commonness follows from Sidorenko’s conjecture when it holds for that graph, while whether common graphs exist at every chromatic number remains open.Sidorenko’s conjecture says random graphs of density p asymptotically minimize the number of copies of a given bipartite graph among graphs of the same order and edge density.Source: §2.6 · p. 19
• The flag algebra method gives c4 > 1/35 and the exact value c3,3 = 1/25.For complete graphs, the best lower bound stated here is c_t ≥ C^−(1+o(1))t^2, where C ≈ 2.18.Source: §2.6 · pp. 19–20
• Fox’s construction strongly disproves the Burr–Rosta conjecture for two colours, and for more than two colours the proposed extension fails as well.For connected H, the two-colour construction gives c_H ≤ (χ(H) −1)^(1−v(H)); the cited three-colour example gives c_H,3 ≤ 2^−(1−o(1))m^3/2/4 for a clique with m edges.Source: §2.6 · p. 20

3 Variants

• The section surveys a small selection of Ramsey-function variants chosen for their perceived importance.Source: §3 · p. 20

3.1 Induced Ramsey numbers

• For every n-vertex graph H, the bound improves to rind(H) ≤ 2^{c n log n}, removing one logarithmic factor from the earlier exponent.The earlier bound was rind(H) ≤ 2^{c n log^2 n}.Source: §3.1 · p. 21
• If λ ≤ 2^{-c n log n}N, every (1/2, λ)-jumbled N-vertex graph forces every n-vertex graph as an induced monochromatic copy in every two-colouring, all in one colour.The improved approach uses pseudorandom graphs; earlier, Kohayakawa, Prömel and Rödl [144] used random graphs built with projective planes, and Fox and Sudakov obtained their bound using explicit pseudorandom graphs.Source: §3.1 · p. 21
• For maximum degree ∆, Conlon, Fox and Zhao [63] prove rind(H) ≤ c n^{2∆+8} for every n-vertex graph H.Source: §3.1 · p. 21
• There are graphs on c n^{2∆+8} vertices whose every two-colouring has one colour containing induced copies of all n-vertex graphs of maximum degree ∆; even the uncoloured universal-copy condition requires Ω(n^{∆/2}) vertices.Source: §3.1 · p. 22
• Open problems ask whether rind(H; q) ≤ 2^{n^{1+o(1)}} for q ≥ 3, and whether bounded-degree graphs admit a polynomial bound with exponent independent of ∆.Theorems 3.3 and 3.4 extend to more than two colours, unlike Theorems 3.1 and 3.2.Source: §3.1 · p. 22

3.2 Folkman numbers

• The lower bound f(t) ≥ 2^(c′t) is essentially the usual Ramsey lower bound, while earlier induction-based constructions required enormous graphs.The Folkman number f(t) is the minimum order of a K_{t+1}-free graph in which every two-colouring forces a monochromatic K_t.Source: §3.2 · p. 22
• The current best bound for f(3) is f(3) ≤ 786, due to Lange, Radziszowski and Xu.Earlier, Spencer, building on Frankl and Rödl, proved f(3) < 10^10; the bound has since improved further.Source: §3.2 · p. 22
• Rödl and Ruciński determined random-graph Ramsey thresholds and used them to give another proof of Folkman’s theorem for q ≥ 2.The stated theorem concerns graphs H that are not forests consisting of stars and paths of length 3.Source: §3.2 · p. 23
• A container-based method gives f(t) ≤ 2^(ct^4 log t).The method also yields a comparable bound for the q-colour analogue f(t; q); the authors conjecture that f(t) is at most exponential in t.Source: §3.2 · p. 23

3.3 The Erd˝os–Hajnal conjecture

• For every fixed graph H, the conjecture asks whether every induced-H-free n-vertex graph has a clique or independent set of order n^c(H); it remains open in general.It holds for H that is a clique or independent set, for all graphs on at most four vertices, and for the bull, but remains open for examples including C5 and P5.Source: §3.3 · p. 24
• The best general bound has not been improved, while Fox and Sudakov give an off-diagonal guarantee and unify Erdős–Hajnal and Prömel–Rödl-type results.For, 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; guarantees every graph on at most k vertices as an induced subgraph or a clique or independent set of order c2^(c′k) log n.Source: §3.3 · p. 24
• For each t, graphs excluding both P_t and its complement as induced subgraphs have the strong Erdős–Hajnal property; the same holds when excluding long cycles and their complements.The strong property also implies the Erdős–Hajnal property for hereditary families, though some proper hereditary families, such as triangle-free graphs, lack the strong property.Source: §3.3 · p. 25
• Convex-set intersection graphs and bounded-complexity semi-algebraic graphs have the strong Erdős–Hajnal property, while string graphs have the Erdős–Hajnal property but not the strong one.For string graphs, the best stated bound is n^c/log log n [111]; curves with each pair intersecting at most k times have the strong property.Source: §3.3 · p. 25
• Every induced-H-free graph contains a complete or empty bipartite graph with polynomial-sized parts, and Fox and Sudakov strengthen this to such a complete bipartite graph or a polynomial-sized independent set.Fox and Sudakov give an induced subgraph of linear order whose density is at most ε or at least 1−ε, and conjecture a polynomial dependence on ε; the section also poses a stronger two-part density problem, including a triangle-free case.Source: §3.3 · pp. 25–26
• The multicolour conjecture predicts a polynomial-sized subset using at most q−1 colours when a q-colouring avoids a fixed coloured complete graph; for q=3, rainbow-triangle-free colourings contain such subsets of size cn^1/3 log^2 n [109].The q=2 case recovers the Erdős–Hajnal conjecture, and the q=3 bound is tight up to a constant factor, answering a question of Hajnal.Source: §3.3 · p. 26
• The tournament analogue is equivalent to the graph conjecture, and Berger, Choromanski and Chudnovsky prove it for every tournament on at most five vertices and an infinite family beyond these.The larger family cannot be obtained through the tournament analogue of the substitution procedure.Source: §3.3 · p. 27
• For k-uniform hypergraphs with k≥4, no standard Erdős–Hajnal analogue holds, but induced-H-free 3-uniform hypergraphs contain complete or empty tripartite subgraphs with parts of order (log n)^1/2+δ(H).The section conjectures a stronger (log n)^1−o(1) bound for 3-uniform hypergraphs.Source: §3.3 · p. 27

3.4 Size Ramsey numbers

• Beck proved that the size Ramsey number of the n-vertex path Pn is at most cn for some constant c.This answered a question of Erdős, Faudree, Rousseau and Schelp [88].Source: §3.4 · p. 27
• Graphs of maximum degree 3 can have superlinear size Ramsey numbers, while bounded-maximum-degree graphs have subquadratic size Ramsey numbers.The cited theorem statements give no further bound values in the supplied passages.Source: §3.4 · p. 28
• Rödl and Szemerédi [184] conjectured that for every Δ≥3, some n-vertex graph of maximum degree Δ has size Ramsey number at least n^(1+ε) for some ε>0.The conjecture applies for all sufficiently large n.Source: §3.4 · p. 28
• For every t, some graph H with chromatic number t attains rχ(H)=(t−1)^2+1, as conjectured by Burr, Erdős and Lovász and established using Zhu and Paul and Tardif.The lower bound and the proof context are described in the passage introducing the result.Source: §3.4 · p. 28
• Kinnersley, Milans and West posed the open question of whether every maximum-degree-Δ graph has degree Ramsey number at most some constant Δ′, for each Δ≥3.For Δ=2, the answer is yes.Source: §3.4 · pp. 28–29
• In the Builder–Painter game, Conlon showed that on-line Ramsey numbers are exponentially smaller than size Ramsey numbers for infinitely many t, while the proposed limiting ratio remains open.The proposed limit is ˜r(t)/ˆr(t)→0 as t→∞.Source: §3.4 · p. 29

3.5.1 The Erd˝os–Gy´arf´as function

• For the colouring function f(n,p,q), every Kp must receive at least q colours; f(n,p,p) is polynomial, while whether f(n,p,p−1) is subpolynomial was a longstanding question.The function f(n,p,2) is the minimum number of colours needed to avoid a monochromatic Kp.Source: §3.5.1 · pp. 29–30
• Conlon, Fox, Lee and Sudakov extended Mubayi’s colouring to answer the subpolynomial-growth question for all p; the section also derives a subpolynomial upper bound for f₃(n,4,3).Mubayi’s construction gives a (4,3)-colouring with e^(c√log n) colours, and Eichhorn and Mubayi extended it to (5,4)-colourings and (p,2⌈log p⌉−2)-colourings for p ≥ 5.Source: §3.5.1 · pp. 30, 32
• For f(n,4,3), the lower bound c′ log n [115] remains far below the upper bound e^(c√log n), and the section poses improving the lower bound beyond logarithmic growth as an open problem.The authors suspect the upper bound may be closer to the truth.Source: §3.5.1 · p. 31
• For the hypergraph generalisation, the authors conjecture that f_k(n,p,k+1) is subpolynomial for all p ≥ k+1; they note that the k = 3 cases p = 4 and 5 require additional ideas.They also connect the k = 3, p = 4 case to Shelah’s cube lemma and Hales–Jewett theorem [192].Source: §3.5.1 · p. 31

3.5.2 The Erd˝os–Rogers function

• Sudakov showed that f_{3,5}(n) is at least n^(5/12), improving the bound by combining the preceding argument with a variant of dependent random choice.Source: §3.5.2 · p. 34
• For every s ≥ 3, f_{s,s+1}(n) = n^(1/2+o(1)), settling the order of the Erdős–Rogers function when t = s + 1.This followed earlier bounds of O(n^(2/3)) by Dudek and Rödl and a matching lower bound up to logarithmic factors for f_{3,4}(n) by Wolfovitz.Source: §3.5.2 · p. 34
• A random graph built from a generalised quadrangle gives f_{3,4}(n) = O(n^(2/3)): it is K4-free, yet every subset of order at least 10n^(2/3) contains a triangle.The construction partitions each line randomly into three parts and takes the complete 3-partite graph on those parts.Source: §3.5.2 · p. 35

3.5.2 The Erdős–Rogers function

• The function has upper bound f_{s,t}(n)≤c_s log n; in particular, f_{s,s+1}(n)≤c_2 log n.Source: §3.5.2 · p. 35
• For s≥3, the lower bound for f^{(k)}_{s,s+1}(n) is (log^(k−2) n)^(1/3−o(1)), and the result extends to higher uniformities.The lower bound improves an earlier exponent of 1/4, but remains far below the upper bound.Source: §3.5.2 · p. 36
• The gap between the upper and lower bounds remains open, including whether f_{s,s+1}(n)=(log n)^o(1).Source: §3.5.2 · p. 36

3.6.1 Weighted cliques

• The matching weighted-clique lower bound uses interval partitions, dependent random choice, and a weighted version of Ramsey’s theorem.The construction seeks intervals whose subsets split into red and blue cliques, with monochromatic edges between each pair of subsets.Source: §3.6.1 · p. 37
• f(n) = Θ(log log log n): every two-colouring of {2, . . . , n} has a monochromatic clique of weight at least this order [83, 60].Theorem 3.37 gives this asymptotic result for sufficiently large n.Source: §3.6.1 · pp. 36–37
• For three colours, the weighted-clique analogue of Erdős’ conjecture fails: a colouring can keep the maximum monochromatic weight bounded as n grows.Colour edges within intervals red and blue as in the two-colour construction, and edges between intervals green.Source: §3.6.1 · p. 37
• f(n, w2) = Θ(log log log log log n), and a further theorem characterizes the convergence boundary for general weights using iterated logarithms.Here w2(i) = 1/(log i log log log i); the general theorem also gives an iterated-log asymptotic for a family of weights.Source: §3.6.1 · p. 38

3.6.2 Cliques of fixed order type

• R(t; q) ≤ 2^(t^(20q)): every q-colouring contains a monochromatic Kt whose consecutive differences have any prescribed order [60].This addresses Väänänen’s question for every permutation of [t−1].Source: §3.6.2 · pp. 38–39
• The natural hypergraph analogue of the prescribed-difference-order question fails: a monochromatic clique forces its consecutive differences to be monotone.Colour each triple red when its last gap is at least its first gap, and blue otherwise.Source: §3.6.2 · p. 39

3.7 Ordered Ramsey numbers

• Cliques have equal ordered and usual Ramsey numbers, r<(Kt)=r(Kt), but sparse graphs can differ substantially; this was shown by Conlon, Fox, Lee and Sudakov and Balko, Cibulka, Král and Kynčl.Source: §3.7 · p. 39
• For every even n, some ordered matching M has r<(M) ≥ n^(c log n/log log n), while all matchings satisfy r<(M) ≤ n⌈log n⌉ and the bound holds for almost all orderings.By contrast, the usual Ramsey number of a matching is linear in its number of vertices.Source: §3.7 · p. 39
• For ordered graphs of degeneracy d, shows that the ordered Ramsey number cannot be too much larger than the usual Ramsey number; the degeneracy ordering need not match the prescribed order.The theorem's bound is parameterized using γ(H)=min{log2(2n/d), d log(2n/d)}.Source: §3.7 · p. 39
• Bounded degeneracy and interval chromatic number χ<(H) yield a polynomial ordered Ramsey number in n [53].The interval chromatic number is the minimum number of consecutive vertex intervals partitioning H into independent sets; proved a weaker version.Source: §3.7 · pp. 39–40
• Bounded-bandwidth ordered graphs have polynomial ordered Ramsey numbers, and for sufficiently large n in terms of ℓ, the exponent constant can be taken as cℓ=O(ℓ).The authors note that the correct cℓ may be significantly smaller.Source: §3.7 · p. 40
• For some even n-vertex matching M, r<(K3,M) ≥ c(n log n)^(4/3), and it remains open whether r<(K3,M)=O(n^(2−ε)) uniformly for some ε>0.The problem asks whether this subquadratic upper bound holds for every matching M on n vertices.Source: §3.7 · p. 40
• For k≥3, the ordered Ramsey number of the monotone k-uniform tight path grows as a (k−2)-fold exponential in n, whereas its unordered Ramsey number grows linearly, (see also).Source: §3.7 · p. 40

4 Concluding remarks

• Conjecture 4.1 asks whether every n-vertex graph contains a regular induced subgraph with ω(log n) vertices.Ramsey’s theorem guarantees one of order at least 1/2 log n, while Alon, Krivelevich and Sudakov showed that some n-vertex graphs have no such subgraph of order at least c n^1/2 log^1/4 n; any polynomial improvement to this upper bound would be significant.Source: §4 · p. 41
• Although almost all colorings of K_{2^t} avoid a monochromatic K_t, Erdős’ probabilistic argument does not construct such a coloring.The argument implies r(t) > 2^t but supplies no constructive procedure.Source: §4 · p. 41
• Frankl and Wilson gave a remarkable explicit Ramsey-graph construction, later improved by Barak, Rao, Shaltiel and Wigderson.The later construction is constructive in that adjacency can be decided in polynomial time from two vertex labels, but it lacks a simple description; achieving its bound, or a significant improvement on Frankl–Wilson’s bound, with a simpler description remains an open question. Explicit graphs exhibiting r(t) > (1 + ε)t also remain elusive.Source: §4 · pp. 41–42