Size-Ramsey numbers of tight paths

Alexey Pokrovskiy; Liana Yepremyan; Shoham Letzter

REVIEW 3 major objections 4 minor 48 references

Size-Ramsey numbers of tight paths

T0 review · 3 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper proves that the s-colour size-Ramsey number of the r-uniform tight path on n vertices is linear in n for every fixed r and s, resolving a 2017 question.

desk verdict Major result—linear size-Ramsey for all tight paths—but there is a real gap in the proof of Lemma 4.24 that needs patching before the paper is complete. read the letter →

arxiv 2507.01498 v1 pith:ZR6MMDUH submitted 2025-07-02 math.CO

Shoham Letzter , Alexey Pokrovskiy , Liana Yepremyan This is my paper · ORCID

classification math.CO MSC 05C5505C6505D10

keywords size-RamseynumbertightpathshypergraphsRamseytheoryexpandersmulticolourorderedforestsmonochromaticwalk

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proves that the $s$-colour size-Ramsey number of the $r$-uniform tight path on $n$ vertices is linear in $n$ for every fixed $r$ and $s$: there is a hypergraph with only $O(n)$ edges whose every $s$-edge-colouring contains a monochromatic copy of the path. The result answers a 2017 question about hypergraph size-Ramsey numbers, and extends earlier work that settled the graph case and the $r=3$ hypergraph case to all uniformities and all numbers of colours. The proof builds the host from a bounded-degree expander graph raised to a large power, and shows through a hierarchy of ordered tree families that any colouring avoiding long monochromatic tight paths would carry an impossible amount of structure. The paper also states that the same machinery yields linear size-Ramsey bounds for powers of tight paths, tight hypergraph trees, and long subdivisions of bounded-degree hypergraphs.

What carries the argument

The argument is carried by a hierarchy of rooted, ordered forests attached to the vertices of a bounded-degree $\varepsilon$-expander graph $G$. The host hypergraph is $G^{p'}$, the $r$-uniform hypergraph whose edges are $r$-tuples of vertices pairwise within distance $p'$ in $G$. A colouring with no long monochromatic tight path is shown to be $k$-disconnected: no short monochromatic tight walk joins two independent $(r-1)$-sets of leaves of the same 'type' in nearby trees. Ramsey properties of powers of expanders (Lemma 3.9) then force either a long monochromatic path in an auxiliary colouring or many disjoint monochromatic cliques; each clique is used to 'augment' the forest into taller trees that remain disconnected, while Lemma 4.25 bounds the possible height of any such disconnected family. The contradiction proves the existence of a long monochromatic tight walk in the original colouring.

What would settle it

A direct refutation would be a sequence of $r$-uniform hypergraphs with $O(n)$ edges and bounded maximum degree whose edges can be $s$-coloured so that every monochromatic tight path has $o(n)$ vertices. Concretely, finding such a construction for $r=3$, $s=2$ for infinitely many $n$ would contradict Theorem 1.1, since the theorem promises that every $O(n)$-edge bounded-degree host forces a monochromatic tight path of linear length.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central claim is Theorem 1.1: for fixed integers $r,s \ge 1$, the $s$-colour size-Ramsey number of the $r$-uniform tight path $P_n^{(r)}$ is $O(n)$. Equivalently, for any fixed uniformity and any fixed number of colours, an $n$-vertex hypergraph with $O(n)$ edges can be built that is Ramsey for that path in every colouring. The stronger technical engine is Theorem 5.1, which produces, for every $r \ge 3$ and $s \ge 2$, a bounded-degree $n$-vertex $r$-uniform hypergraph in which every $s$-colouring contains a monochromatic tight walk of length $\Omega(n)$ that uses each vertex only a bounded number of times; a short blow-up argument converts such a walk into an actual tight path. This settles in the affirmative the 2017 question and supersedes the previous $O((n \log n)^{r/2})$ upper bound for $r \ge 4$.

Load-bearing premise

The load-bearing premise is that arbitrarily large connected expander graphs of bounded degree exist for every small expansion parameter; the paper cites this to an unpublished companion manuscript and offers only a brief probabilistic sketch, yet the host hypergraph cannot be built without such graphs.

Editorial extensions

If this is right

For every fixed $r$ and $s$, $\hat{r}_s(P_n^{(r)}) = O(n)$, so the size-Ramsey number matches the order of the number of vertices of the target path.
The result holds for an arbitrary fixed number of colours, not just two, and the host hypergraph can be chosen with maximum degree bounded by a constant depending only on $r$ and $s$.
The earlier upper bound $O((n \log n)^{r/2})$ for $r \ge 4$ is improved to linear, and the $r=3$ case is recovered as a special case.
A monochromatic tight walk with bounded vertex repetition can be converted into a genuine monochromatic tight path, so the proof's walk-based formulation directly implies the path statement.
According to the paper, the same proof approach also gives linear size-Ramsey numbers for powers of tight paths, tight hypergraph trees, and long subdivisions of bounded-degree hypergraphs.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Beyond the paper: the constants hidden in the $O(n)$ bound grow rapidly with $r$ and $s$, and known lower bounds suggest the linear coefficient genuinely depends on both parameters; determining the correct order in $r$ and $s$ is a natural next problem.
Beyond the paper: the expander-power construction is a plausible template for proving linear size-Ramsey bounds for other sparse hypergraph families, such as bounded-degree tight trees or grid-like hypergraphs, by adapting the tree-hierarchy and type machinery.
Beyond the paper: the contradiction is formulated in terms of monochromatic tight walks with bounded vertex repetition, a stronger notion than simple paths, so the method may transfer to 'blow-up Ramsey' problems or to structured walks in other sparse hypergraphs.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

You should know two things about arXiv:2507.01498. First, it proves the right theorem: linear s-colour size-Ramsey numbers for r-uniform tight paths for every fixed r and s, settling the 2017 question of Dudek, La Fleur, Mubayi and Rödl. Second, the proof is not yet fully clean—the application of Lemma 4.17 inside Lemma 4.24 appears to be outside that lemma's hypotheses, and this step powers the final contradiction in Theorem 5.1.

What's genuinely new and good: for r ≥ 4 the previous bound was superlinear (Lu–Wang), so this is a real breakthrough, not an incremental improvement. The machinery—ordered forest families, types, k-disconnected colourings, augmentations, versatile sets—is substantial and most of it is carefully defined. The proof of Theorem 1.1 from the technical Theorem 5.1 is short and elegant, and the expander-power approach is a natural generalization of the graph-path argument. The paper also gives a good overview that makes the structure navigable. Reliance on the authors' own unpublished [38] for the existence of expanders is mild; the statement is standard and a sketch is given.

Soft spots: the Lemma 4.24 issue is the main one. Lemma 4.17 requires a V(H)-forest, but T is rooted at its top, not at its leaves, and the complete hypergraph on L(T) has unbounded degree, so the lemma's hypotheses fail. The intended statement—a binary subtree on which all r-sets of the same type have the same colour—is plausible and can be obtained by iterating Lemma 4.16 over the finitely many types, but that argument isn't written down. Since Lemma 4.25 and hence Theorem 5.1 rest on Lemma 4.24, the proof as currently written has a load-bearing gap. I'd guess it's fixable, but it's real. There are also some smaller typos (Lemma 3.9's 'colour 1' vs 'colour d+1', the arity confusion in the Theorem 5.1 summary) and compressed justifications elsewhere, which together slow independent verification.

Who should read it: anyone working on size-Ramsey numbers or Ramsey properties of expanders. It deserves a serious referee—a good referee will want to check Lemma 4.24 and the cleaning argument carefully. My recommendation: send it to peer review, with a note asking the referee to focus on Section 4.2 and Lemma 4.24. If the authors patch that gap, this will be a strong paper.

Referee Report

3 major / 4 minor

Summary. The paper proves that the s-colour size-Ramsey number of the r-uniform tight path P_n^{(r)} is O(n) for every fixed r and s, answering a question of Dudek, La Fleur, Mubayi and Rödl (2017). The proof constructs a bounded-degree expanding graph G and shows that an appropriate power G^p, viewed as an r-uniform hypergraph, is Ramsey for tight paths. The main technical engine is Theorem 5.1, which asserts the existence of bounded-degree r-uniform hypergraphs on n vertices in which every s-colouring contains a long monochromatic tight walk with bounded vertex multiplicity. The proof introduces ordered forests, types of leaf subsets, clean colourings, disconnected tree assignments, and versatile sets, and culminates in a structural contradiction (Lemma 4.25). The final section derives the size-Ramsey bound from Theorem 5.1 via a blow-up argument.

Significance. The result resolves an open problem from Dudek, La Fleur, Mubayi and Rödl (2017), extending the known case r = 3 and improving the best previous bound for r ≥ 4. The paper introduces a substantial new toolkit for hypergraph size-Ramsey problems, and the overall strategy is coherent and ambitious. If the technical gaps identified below are repaired, the paper would be a significant contribution to extremal combinatorics. The final blow-up argument is clean, and the dependence on expanders is standard; the paper also gives a concise reduction of the main theorem to a single structural statement (Theorem 5.1).

major comments (3)

[Section 4.3, Lemma 4.24] The proof of Lemma 4.24 applies Lemma 4.17 to the tree T, but Lemma 4.17 requires an r-uniform hypergraph H of maximum degree at most Δ and a V(H)-forest F. Here H is the complete r-uniform hypergraph on L(T), whose maximum degree is unbounded (it is binomial in |L(T)|), and T is not a V(H)-forest with V(H) = L(T). Since Lemma 4.25 and hence Theorem 5.1 rely on Lemma 4.24, this is a load-bearing gap. The desired statement is plausible and can be proved by iterating Lemma 4.16 over the finite set Types(h, r), reducing the arity by a controlled amount at each step; please provide this argument explicitly.
[Section 4.3, Observation 4.19 and Lemma 4.25] Observation 4.19 is false as stated: the claimed equivalence between e being an edge of G^t ⊗_r F and ||e||_G ≤ t fails for r-sets e with fewer than r distinct π0-values, because {v} need not be contained in any r-edge of G^t. For example, if G is a path, t = 1, and r = 3, then G^1 has no edges and no r-subset of L(F(v)) with π0(e) = {v} is an edge, yet ||e||_G = 0. The proof of Lemma 4.25 uses this false converse to conclude that the sequence P constructed from Lemma 4.24 is a tight walk in G^t ⊗ F. In the intended application (t = c_h ≥ 2 and G an expander with Δ ≫ r) the needed direction does hold, because every vertex has at least r vertices in its closed neighbourhood and all r-subsets of L(F(v)) are then contained in edges of G^{c_h}; but the paper must state and prove this, and the statement of Lemma 4.25 should be restricted to the range where the complete hypergraph on L(F(v)) embeds into G^t ⊗ F.
[Section 4.3, Lemma 4.25] Lemma 4.25 is stated for every non-negative integer t, but it is false for small t: if G is a path and t = 1 with r = 3, then G^1 ⊗ F has no edges, so every colouring is vacuously 1-disconnected regardless of the height of F. The proof implicitly assumes that every r-subset of leaves with constant π0 is an edge, which requires t large enough relative to the local structure of G. Since Theorem 5.1 only needs t = c_h for the large constants produced by the hierarchy, the lemma should be reformulated for that range, with the missing embedding argument supplied.

minor comments (4)

[Lemma 3.9] In the proof of Lemma 3.9, 'we either get a colour 1 copy of K_d' should read 'colour d+1' (or 'colour s+1'), since the K_d in Lemma 3.8 is in the last colour, not colour 1.
[Theorem 5.1] In the final paragraph of the proof of Theorem 5.1, 'a balanced d_h-ary V(G)-forest' and 'G^{d_h} ⊗ F_h' should be 'c_h-ary' and 'G^{c_h} ⊗ F_h', consistent with properties (F2) and (F5).
[Lemma 4.25] The statement assumes r ≤ s, but the proof does not use this inequality. If the result is intended for all s, remove the restriction; otherwise, Theorem 5.1's application for r > s needs a short reduction (e.g., viewing an s-colouring as an r-colouring with unused colours).
[Sections 2–3] The notation G^k is defined as the r-uniform hypergraph power, but in Section 3 (Lemmas 3.7–3.9) it is used for the ordinary graph power; please disambiguate, for instance by writing G^k_{(r)} for the hypergraph in the Ramsey lemmas or by explicitly saying that Section 3 uses graph powers.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: the size-Ramsey bound is obtained from a self-contained Ramsey engine, with one standard self-cited expander fact and one non-circular proof gap.

full rationale

Theorem 1.1 is derived from Theorem 5.1 by a direct blow-up argument: Theorem 5.1 provides a bounded-degree host H with a long monochromatic tight walk, and the proof converts that walk to a tight path in H[d] using the cleaning lemma (Lemma 4.17) and the repetition bound from Theorem 5.1; the target statement is not assumed at any point. Theorem 5.1 is proved by building forests F_i and invoking Lemma 4.25 for the final contradiction, with no fitted parameter or renamed known result. Two caveats deserve explicit flags, but neither is circular. (1) Lemma 3.2, the existence of arbitrarily large bounded-degree epsilon-expanders, is cited to the authors' own unpublished manuscript [38]: 'It is a standard result that there exist arbitrarily large epsilon-expanders of bounded degree (e.g. G(n, C/n) satisfies this after deleting high degree vertices. See [38], Proposition 3.2).' This is a self-citation, but it is a parameter-free existence fact whose stated assumptions do not include the size-Ramsey conclusion, and the paper itself gives the G(n,C/n) probabilistic sketch, so it is independent support rather than circular dependence. (2) In Lemma 4.24, the line 'By Lemma 4.17 applied to T, there is a balanced binary subtree T′ ≤ T of height h, such that r-sets of leaves of the same type have the same colour' applies Lemma 4.17 outside its stated hypotheses: Lemma 4.17 requires an r-uniform hypergraph H of maximum degree at most Δ and a V(H)-forest, while the natural H here is the complete r-uniform hypergraph on L(T), whose maximum degree is unbounded, and T is not a V(H)-forest on L(T). This is a load-bearing proof gap (the claim is plausible via iteration of Lemma 4.16), but it is a missing-support or correctness issue, not a reduction of the theorem to its own input. No equation or construction in the paper identifies the predicted quantity with a fitted parameter or with the theorem's hypothesis, so the circularity score is 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central claim rests on standard background results (expanders, Ramsey's theorem, basic probabilistic bounds) plus the paper's own internal lemmas. No empirical free parameters are used; the constants in the hierarchy p >> p' >> ... are chosen to satisfy inequalities, not fitted to data.

assumptions (5)

domain assumption Existence of arbitrarily large connected epsilon-expanders with maximum degree epsilon^{-2} (Lemma 3.2).
The host graph G is taken to be such an expander; cited to the authors' own [38] with a probabilistic sketch. Standard in graph theory, but an external premise.
standard math Path-partition lemma of [6]: every graph can be partitioned into a path P and two equal-size sets A,B with no edges between A and B (used in Lemma 3.3).
Used to prove the bipartite Ramsey lemma 3.3, which underpins Lemmas 3.4, 3.5, 3.8 and 3.9. Cited, not proved in the paper.
standard math Ramsey's theorem (used in Lemmas 3.5, 4.16, 4.24 and in the cleaning lemma 4.17).
Standard background result in Ramsey theory.
standard math Chernoff bounds (used in Lemma 4.14 to find disjoint subtrees).
Standard probabilistic tail bound.
standard math The line graph of an r-uniform hypergraph with maximum degree Delta has chromatic number at most r*Delta + 1 (used in Lemma 4.17 to partition edges into matchings).
Standard greedy coloring argument.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Size-Ramsey numbers of tight paths." pith.science (2026). https://pith.science/paper/ZR6MMDUH

@misc{pith2026250701498,
  author       = {Pith},
  title        = {Pith review of: Size-Ramsey numbers of tight paths},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZR6MMDUH}},
  note         = {Machine review of arXiv:2507.01498}
}

abstract

The $s$-colour size-Ramsey number of a hypergraph $H$ is the minimum number of edges in a hypergraph $G$ whose every $s$-edge-colouring contains a monochromatic copy of $H$. We show that the $s$-colour size-Ramsey number of the $r$-uniform tight path on $n$ vertices is linear in $n$, for every fixed $r$ and $s$, thereby answering a question of Dudek, La Fleur, Mubayi and R\"odl (2017).

Figures

Figures reproduced from arXiv: 2507.01498 by the authors.

**Figure 1.** A height 3 ordered tree with the natural labelling in N 3 Definition 4.3 (L(F) and AF (S)). Given an ordered forest F, we write L(F) for the (ordered) set of leaves of F (i.e. vertices with out-degree 0). Given a set of vertices S ⊆ V (F), we let AF (S) be the induced subforest of F consisting of all ancestors of vertices of S (see [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗

**Figure 2.** A set of leaves S and the corresponding AF (S) for any set of leaves S in a forest F we have L [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗

**Figure 3.** A forest F (on the left) and the forest F − (on the right) Lemma 4.8. For X ⊆ L(F), we have AF − (X) = (AF (X))−. Proof. By definition, V A F − (X) = {y ∈ V (F −) : y is an ancestor of some x ∈ X} = {y ∈ V (F) \ root(F) : y is an ancestor of some x ∈ X} = {y ∈ V (F) : y is an ancestor of some x ∈ X} \ root(F) = V [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗

Figures from the paper (4 more)

**Figure 4.** Figure 4: Two independent sets of leaves e, f and the corresponding ancestors ve, vf Observation 4.21. If e, f are independent sets of leaves in an S-forest, then |π0(e)| = |π0(f)| = 1. Proof. Let all of e descend from ve = (x, y). By definition of edges in S-forests, all desce…

**Figure 5.** Figure 5: An illustration of the sets {v0, . . . , vh}, {u0, . . . , uh}, {w1, . . . , wℓ} and {w ′ 1 , . . . , w′ h }; here the leaves are ordered from left to right. By Ramsey’s theorem there is a subset A ⊆ {u0, . . . , uh} of size 2ℓ + 1 whose r-subsets all have the same col…

**Figure 6.** Figure 6: An illustration of a forest F ′ (in blue) which is an augmentation of a forest F (in black) The following lemma gives us the properties of augmentation we use. Lemma 4.35 (Properties of augmentation). Let G be a graph and F, F′ be V (G)-forests with F ′ augmenting F. T…

**Figure 7.** Figure 7: ). It is useful to note that isomorphisms map extendible paths to extendible paths [PITH_FULL_IMAGE:figures/full_fig_p020_7.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

48 extracted references · 43 canonical work pages

[38]

Letzter, A

S. Letzter, A. Pokrovskiy, and L. Yepremyan,Size-Ramsey numbers of powers of hypergraph trees and long subdivisions , arXiv:2103.01942 (2021). 3, 5, 27

arXiv 2021
[1]

Allen and J

P. Allen and J. B¨ ottcher, Partition universality for graphs of bounded degeneracy and degree, (2022), arXiv:2211.15819. 2

arXiv 2022
[2]

Bal and L

D. Bal and L. DeBiasio, New lower bounds on the size-Ramsey number of a path , Electron. J. Combin. 29 (2022), P1.18. 2

work page 2022
[3]

D. Bal, L. DeBiasio, and A. Lo, A lower bound on the multicolor size-Ramsey numbers of paths in hypergraphs, Eu. J. Combin. 120 (2024), 103969. 3

work page 2024
[4]

Beck, On size Ramsey number of paths, trees, and circuits

J. Beck, On size Ramsey number of paths, trees, and circuits. I , J. Graph Theory 7 (1983), 115–129. 2, 3

work page 1983
[5]

II , Mathematics of Ramsey Theory, Springer Berlin Heidelberg, Berlin, Heidelberg, 1990, pp

, On size Ramsey number of paths, trees and circuits. II , Mathematics of Ramsey Theory, Springer Berlin Heidelberg, Berlin, Heidelberg, 1990, pp. 34–45. 2

work page 1990
[6]

Ben-Eliezer, M

I. Ben-Eliezer, M. Krivelevich, and B. Sudakov, Long cycles in subgraphs of (pseudo)random directed graphs, J. Graph Theory 70 (2012), 284–296. 5

work page 2012
[7]

Berger, S

Y. Berger, S. Kohayakawa, G. S. Maesaka, T. Martins, W. Mendon¸ ca, G. O. Mota, and O. Parczyk, The size-Ramsey number of powers of bounded degree trees , J. London Math. Soc. 103 (2021), 1314–1332. 3

work page 2021

Show all 48 references

[8]

Bollob´ as,Extremal graph theory with emphasis on probabilistic methods , no

B. Bollob´ as,Extremal graph theory with emphasis on probabilistic methods , no. 62, Ameri- can Math. Soc., 1986. 2

1986
[9]

73, Cambridge university press, 2001

, Random graphs, no. 73, Cambridge university press, 2001. 2

2001
[10]

Campos, S

M. Campos, S. Griffiths, R. Morris, and J. Sahasrabudhe, An exponential improvement for diagonal Ramsey, (2023), arXiv:2303.09521. 1

2023 arXiv
[11]

Campos, M

M. Campos, M. Jenssen, M. Michelen, and J. Sahasrabudhe, A new lower bound for the Ramsey numbers R(3, k), (2025), arXiv:2505.13371. 1

2025 arXiv
[12]

Clemens, M

D. Clemens, M. Jenssen, Y. Kohayakawa, N. Morrison, G. O. Mota, D. Reding, and B. Roberts, The size-Ramsey number of powers of paths , J. Graph Theory 91 (2019), 290–299. 3

2019
[13]

Clemens, M

D. Clemens, M. Miralaei, D. Reding, M. Schacht, and A. Taraz,On the size-Ramsey number of grid graphs , Combin. Probab. Comput. 30 (2021), no. 5, 670–685. 27

2021
[14]

Conlon, Question suggested for the ATI–HIMR Focused Research Workshop: Large– scale structures in random graphs, Alan Turing Institute, December, 2016

D. Conlon, Question suggested for the ATI–HIMR Focused Research Workshop: Large– scale structures in random graphs, Alan Turing Institute, December, 2016. 3

2016
[15]

, A new upper bound for diagonal Ramsey numbers , Ann. Math. 170 (2009), no. 2, 941–960. 1

2009
[16]

Conlon, R

D. Conlon, R. Nenadov, and M. Truji´ c, The size-Ramsey number of cubic graphs , Bull. London Math. Soc. 54 (2022), no. 6, 2135–2150. 2

2022
[17]

, On the size-Ramsey number of grids , Combin. Probab. Comput. 32 (2023), no. 6, 874–880. 27

2023
[18]

Dragani´ c, M

N. Dragani´ c, M. Kaufmann, D. Munh´ a Correia, K. Petrova, and R. Steiner,Size-Ramsey numbers of structurally sparse graphs , (2023), arXiv:2307.12028. 2 28

2023 arXiv
[19]

Dragani´ c, M

N. Dragani´ c, M. Krivelevich, and R. Nenadov, Rolling backwards can move you forward: on embedding problems in sparse expanders, Trans. Am. Math. Soc. 375 (2021), 5195–5216. 3, 27

2021
[20]

Dragani´ c and K

N. Dragani´ c and K. Petrova,Size-Ramsey numbers of graphs with maximum degree three , J. London Math. Soc. 111 (2025), no. 3, e70116. 2

2025
[21]

Dudek, S

A. Dudek, S. La Fleur, D. Mubayi, and V. R¨ odl,On the size-Ramsey number of hypergraphs, J. Graph Theory 86 (2017), 104–121. 3, 27

2017
[22]

Dudek and P

A. Dudek and P. Pra lat, An alternative proof of the linearity of the size-Ramsey number of paths, Combin. Probab. Comput. 24 (2015), 551–555. 2

2015
[23]

, On some multicolor Ramsey properties of random graphs , SIAM J. Discr. Math. 31 (2017), 2079–2092. 2

2017
[24]

, Note on the multicolour size-Ramsey number for paths , Electron. J. Combin. 25 (2018), P3.35. 2

2018
[25]

Erd˝ os,Some remarks on the theory of graphs , Bull

P. Erd˝ os,Some remarks on the theory of graphs , Bull. Amer. Math. Soc. 53 (1947), no. 12, 292–294. 1

1947
[26]

Erd˝ os and G

P. Erd˝ os and G. Szekeres,A combinatorial problem in geometry , Compositio mathematica 2 (1935), 463–470. 1

1935
[27]

Erd˝ os, R

P. Erd˝ os, R. J. Faudree, C. C. Rousseau, and R. H. Schelp, The size Ramsey number , Period. Math. Hung. 9 (1978), 145–161. 2

1978
[28]

Friedman and N

J. Friedman and N. Pippenger, Expanding graphs contain all small trees , Combinatorica 7 (1987), 71–76. 2

1987
[29]

R. L. Graham and V. R¨ odl, Numbers in Ramsey theory , Surveys in combinatorics 123 (1987), 111–153. 1

1987
[30]

J. Han, M. Jenssen, Y. Kohayakawa, G. O. Mota, and B. Roberts, The multicolour size- Ramsey number of powers of paths , J. Combin. Theory, Ser. B 145 (2020), 359–375. 3

2020
[31]

J. Han, Y. Kohayakawa, S. Letzter, G. O. Mota, and O. Parczyk, The size-Ramsey number of 3-uniform tight paths , Adv. Combin. (2021). 3

2021
[32]

P. E. Haxell, Y. Kohayakawa, and T. Luczak, The induced size-Ramsey number of cycles , Combin. Probab. Comput. 4 (1995), 217–239. 2

1995
[33]

Kamˇ cev, A

N. Kamˇ cev, A. Liebenau, D. Wood, and L. Yepremyan,The size Ramsey number of graphs with bounded treewidth, SIAM J. Disc. Math. 35 (2021), 281–293. 3

2021
[34]

Kohayakawa, T

Y. Kohayakawa, T. Retter, and V. R¨ odl,The size Ramsey number of short subdivisions of bounded degree graphs, Random Struct. Algorithms 54 (2019), 304–339. 3

2019
[35]

Kohayakawa, V

Y. Kohayakawa, V. R¨ odl, M. Schacht, and E. Szemer´ edi,Sparse partition universal graphs for graphs of bounded degree , Adv. Math. 226 (2011), 5041–5065. 2

2011
[36]

Krivelevich, Long cycles in locally expanding graphs, with applications , Combinatorica 39 (2019), 135–151

M. Krivelevich, Long cycles in locally expanding graphs, with applications , Combinatorica 39 (2019), 135–151. 2

2019
[37]

Letzter, Path Ramsey number for random graphs , Combin

S. Letzter, Path Ramsey number for random graphs , Combin. Probab. Comput. 25 (2016), 612–622. 2 29

2016
[39]

Lu and Z

L. Lu and Z. Wang, On the size-Ramsey number of tight paths , SIAM J. Discr. Math. 32 (2018), 2172–2179. 3

2018
[40]

Nenadov, Ramsey and universality properties of random graphs , Ph.D

R. Nenadov, Ramsey and universality properties of random graphs , Ph.D. thesis, ETH Z¨ urich, 2016. 2

2016
[41]

Pak, Mixing time and long paths in graphs , Symposium on Discrete Algorithms: Pro- ceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, vol

I. Pak, Mixing time and long paths in graphs , Symposium on Discrete Algorithms: Pro- ceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, vol. 6, 2002, pp. 321–328. 3

2002
[42]

F. P. Ramsey, On a problem of formal logic , Proc. London Math. Soc. 30 (1930), 264–286. 1

1930
[43]

R¨ odl and E

V. R¨ odl and E. Szemer´ edi,On size Ramsey numbers of graphs with bounded degree , Com- binatorica 20 (2000), 257–262. 2, 27

2000
[44]

Sah, Diagonal Ramsey via effective quasirandomness , Duke Math

A. Sah, Diagonal Ramsey via effective quasirandomness , Duke Math. J. 172 (2023), no. 3, 545–567. 1

2023
[45]

Spencer, Asymptotic lower bounds for ramsey functions , Discr

J. Spencer, Asymptotic lower bounds for ramsey functions , Discr. Math. 20 (1977), 69–76. 1

1977
[46]

Thomason, An upper bound for some Ramsey numbers , J

A. Thomason, An upper bound for some Ramsey numbers , J. Graph Theory 12, 509–517. 1
[47]

Tikhomirov, On bounded degree graphs with large size-Ramsey numbers, Combinatorica 44 (2024), 9–14

K. Tikhomirov, On bounded degree graphs with large size-Ramsey numbers, Combinatorica 44 (2024), 9–14. 2, 27

2024
[48]

Winter, Lower bound on the size-Ramsey number of tight paths , J

C. Winter, Lower bound on the size-Ramsey number of tight paths , J. Combin. 14 (2023), 271–279. 3 30

2023

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.

[1] [38]

Letzter, A

S. Letzter, A. Pokrovskiy, and L. Yepremyan,Size-Ramsey numbers of powers of hypergraph trees and long subdivisions , arXiv:2103.01942 (2021). 3, 5, 27

arXiv 2021

[2] [1]

Allen and J

P. Allen and J. B¨ ottcher, Partition universality for graphs of bounded degeneracy and degree, (2022), arXiv:2211.15819. 2

arXiv 2022

[3] [2]

Bal and L

D. Bal and L. DeBiasio, New lower bounds on the size-Ramsey number of a path , Electron. J. Combin. 29 (2022), P1.18. 2

work page 2022

[4] [3]

D. Bal, L. DeBiasio, and A. Lo, A lower bound on the multicolor size-Ramsey numbers of paths in hypergraphs, Eu. J. Combin. 120 (2024), 103969. 3

work page 2024

[5] [4]

Beck, On size Ramsey number of paths, trees, and circuits

J. Beck, On size Ramsey number of paths, trees, and circuits. I , J. Graph Theory 7 (1983), 115–129. 2, 3

work page 1983

[6] [5]

II , Mathematics of Ramsey Theory, Springer Berlin Heidelberg, Berlin, Heidelberg, 1990, pp

, On size Ramsey number of paths, trees and circuits. II , Mathematics of Ramsey Theory, Springer Berlin Heidelberg, Berlin, Heidelberg, 1990, pp. 34–45. 2

work page 1990

[7] [6]

Ben-Eliezer, M

I. Ben-Eliezer, M. Krivelevich, and B. Sudakov, Long cycles in subgraphs of (pseudo)random directed graphs, J. Graph Theory 70 (2012), 284–296. 5

work page 2012

[8] [7]

Berger, S

Y. Berger, S. Kohayakawa, G. S. Maesaka, T. Martins, W. Mendon¸ ca, G. O. Mota, and O. Parczyk, The size-Ramsey number of powers of bounded degree trees , J. London Math. Soc. 103 (2021), 1314–1332. 3

work page 2021