REVIEW 1 major objections 4 minor 1 cited by
Unavoidable subgraphs in Ramsey graphs
T0 review · 1 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read This paper establishes a precise dichotomy: for cycles and balanced complete multipartite graphs every forest of copies is forced in every Ramsey graph with sufficiently many colours, while for infinitely many other graphs there exist…
desk verdict A sharp dichotomy for unavoidable forests of copies in Ramsey graphs, built on the girth Ramsey theorem; the load-bearing ordered hypergraph variant needs a proof or a citation. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The engine is the girth Ramsey theorem (Theorem 1.2): for any graph $F$ and integers $r$ and $\ell$ there is a Ramsey graph $G \to (F)_r$ with a system of copies in which every subfamily of at most $\ell$ copies can be covered by a forest of copies—a set of copies of $F$ glued along single vertices or shared edges. For the negative results, the paper invokes an ordered-linear-hypergraph variant (Theorem 3.1) and a corollary (Corollary 3.4) that, for $(e,v)$-inseparable ordered hypergraphs, makes all induced copies respect the prescribed ordering. The positive direction relies on a set-mapping partition theorem to colour edges so that a monochromatic copy would contradict a maximal glued copy $(m,F)$, forcing the presence of the entire forest. The graphs $F$ of Theorem 1.4 arise from ordered linear 3-uniform hypergraphs $S$ by putting $xz$ in $E(F)$ whenever some $xyz \in E(S)$ with $x < y < z$, which transfers forest structure from $S$ to $F$. The 2-density $m_2(F)$ controls Theorems 1.5 and 1.6: forests of copies do not raise $m_2$, while overlapping or cyclic unions of copies do, so Ramsey graphs must contain configurations heavier than $m_2(F)$.
What would settle it
Two checks would settle the claims: (1) inspect whether the proof of the girth Ramsey theorem for graphs in [10] extends verbatim to ordered linear hypergraphs as Theorem 3.1 requires; (2) for $n=16$ and $r=2$, build the graph $F$ from Proposition 4.1 and the Ramsey graph $G$ from Corollary 3.4, then look for two induced copies of $F$ in $G$ that share an edge without a common third vertex non-adjacent to that edge, or for any non-induced copy of $F$—either would refute Theorem 1.4.
Extended reading notes
Core claim
The central assertion is a dichotomy about unavoidable substructures in Ramsey graphs. Theorem 1.3 asserts that when $F$ is a cycle or a balanced complete multipartite graph with at least two edges, every forest of copies of $F$ is forced: for every such forest $\mathcal{F}$ there is an $r \ge 2$ such that every graph $G$ with $G \xrightarrow{\mathrm{n.n.i.}} (F)_r$ contains a subgraph isomorphic to $\bigcup \mathcal{F}$. Theorem 1.4 asserts that the dichotomy has a negative side: there exist infinitely many graphs $F$ such that for every $r \ge 2$ there is a Ramsey graph $G \to (F)_r$ in which all copies of $F$ are induced, and any two induced copies sharing an edge also share a third vertex not adjacent to either endpoint, so no non-trivial forest of copies occurs. Theorems 1.5 and 1.6 add that Ramsey graphs can be made locally non-Ramsey on every fixed vertex set and can contain $F$-free subgraphs with a positive fraction of the edges inside every subgraph, with Theorem 1.8 (every graph containing a cycle is Ramsey infinite) following from Theorem 1.5.
Load-bearing premise
The load-bearing premise is that the girth Ramsey theorem extends to ordered linear uniform hypergraphs (Theorem 3.1), a statement the paper invokes without proof; if that variant fails, the constructions behind the negative results lose their support.
Editorial extensions
If this is right
- For cycles and balanced complete multipartite graphs, every glued forest of copies is unavoidable in every Ramsey graph with sufficiently many colours.
- For infinitely many dense, 4-connected graphs $F$, there are Ramsey graphs in which all copies are induced and edge-sharing copies always share a non-adjacent third vertex, so no non-trivial forest of copies exists.
- Ramsey graphs for any graph containing a cycle can be made locally non-Ramsey: every $n$-vertex subgraph fails the two-colour non-induced Ramsey property for $F$, and consequently every such $F$ is Ramsey infinite.
- For certain bipartite graphs $F$, every subgraph of a suitable Ramsey graph contains an $F$-free subgraph carrying at least $(\ell(F)-1)/(2\ell(F))$ of its edges.
Reading between the lines
- The dichotomy suggests a natural research direction: characterise the graphs $F$ for which all forests of copies are unavoidable; cycles and balanced complete multipartite graphs may be the first members of a larger family, and strict 2-balancedness or edge-transitivity could be the distinguishing invariant.
- Because Theorems 1.4 and 1.6 rely on the unproved ordered-hypergraph variant (Theorem 3.1), supplying a proof of that variant would immediately secure the negative results; conversely, any failure of Theorem 3.1 would likely produce a concrete counterexample to Theorem 1.4.
- The construction of $F$ from sum-constrained 3-uniform hypergraphs is tied to additive combinatorics; replacing the equations $x+y+z=n$ or $2n$ by other linear forms may yield families of graphs $F$ with even stronger local restrictions, such as forbidding any two copies from sharing a vertex.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies which subgraphs are unavoidable in Ramsey graphs for a given graph F, both in the induced and the non-necessarily-induced edge-Ramsey senses. It builds on the girth Ramsey theorem of Reiher and Rödl (Theorem 1.2) and states an ordered, linear hypergraph version of that theorem (Theorem 3.1). The main new results are: Theorem 1.3, showing that for every cycle or balanced complete multipartite graph F and every forest of copies of F, every Ramsey graph for F with sufficiently many colours contains a subgraph isomorphic to the union of that forest; Theorem 1.4, constructing infinitely many graphs F for which there are Ramsey graphs in which all copies of F are induced and any two copies sharing an edge also share a third vertex non-adjacent to that edge; Theorem 1.5, producing Ramsey graphs that are locally not 2-Ramsey for any graph containing a cycle; and Theorem 1.6, giving bipartite graphs F for which there are Ramsey graphs containing F-free subgraphs with positive density. The paper also derives Theorem 1.8, that every graph containing a cycle is Ramsey infinite, as a consequence of Theorem 1.5. The proofs of the positive results and of the auxiliary propositions about 2-density are given in detail, while the proof of Theorem 1.4 and part of the proof of Theorem 1.6 rely essentially on Theorem 3.1.
Significance. If the standing theorems are accepted, the paper makes a solid contribution to Ramsey theory. The dichotomy expressed by Theorems 1.3 and 1.4 is natural and answers a converse question to the girth Ramsey theorem in a clean way. The paper contains several fully worked technical ingredients, including the set-mapping arguments in Lemmas 2.2 and 2.3, the separability argument in Lemma 3.3, the explicit construction of infinitely many (e,v)-inseparable 3-uniform hypergraphs in Proposition 4.1, and the detailed density calculations in Propositions 5.1 through 5.4. Corollary 5.5, which says that forests of copies of a cyclic graph are not 2-Ramsey, is an elegant and useful observation. The main caveat is that the ordered hypergraph girth Ramsey theorem, Theorem 3.1, is used as a black box without proof or explicit citation; this theorem is load-bearing for the negative results in Theorems 1.4 and 1.6.
major comments (1)
- [Section 3, Theorem 3.1] Theorem 3.1 is stated without proof and without an explicit citation. The sentence introducing it says the variant 'can be stated as follows,' and the reference [10] is given only for the graph version, Theorem 1.2. The ordered hypergraph statement is not a notational restatement of Theorem 1.2: it concerns k-uniform linear hypergraphs, a total order on vertices, ordered induced copies, and a parameter n for the size of a family of copies. The proof of Corollary 3.4 uses Theorem 3.1 for all three properties (i)--(iii), and Corollary 3.4 is then used in the proofs of Theorem 1.4 (Section 4.2) and Theorem 1.6 (Section 6). Please provide a proof of Theorem 3.1, or give an exact pointer to the statement in [10] and derive the present formulation from it.
minor comments (4)
- [Section 2.2, final paragraph] The cycle case of Theorem 1.3 is not fully written out: the final sentence says that the proof imitates the complete multipartite case and omits the details. Since Lemma 2.3 is proved in full, this is a presentation gap rather than a fundamental one, but a short paragraph showing the induction step would make the proof self-contained.
- [Section 4.1, Claim 4.2] The proof of the minimum degree claim says 'one can check' and lists four intervals for I(x); expanding the verification would improve readability, especially because the interval definitions and the counting of pairs {a,b} are central to the degree bound.
- [Section 4.2, Claim 4.5] The sentence 'since F* is 4-connected, we arrive at V(F*)=V(S_t)' is quite terse; a few explanatory sentences about how the 4-connectivity rules out vertices of F* outside S_t would help the reader follow the minimality argument.
- [Section 5.1, Proposition 5.1] The notation F is used both for the forest of copies and for the graph F = union F; although the context is usually clear, a distinct symbol for the forest would remove the ambiguity, especially in the proof of Proposition 5.1.
Circularity Check
No definitional circularity; the derivation chain is deductive, but Theorem 3.1 is stated without proof or explicit citation and is load-bearing for the negative results, a support gap rather than a circular reduction.
full rationale
I walked the claimed derivation chain. Theorem 1.3 is proved from the de Bruijn-Erdős set-mapping theorem and Lemmas 2.2 and 2.3, with no fitted input and no self-referential normalization. Theorem 1.5 follows from Theorem 1.2 and Corollary 5.5, whose proof uses 2-density arguments; none of these steps defines its conclusion in terms of its premises. Theorems 1.4 and 1.6 are derived in Sections 4.2 and 6 from Corollary 3.4, which is proved in Section 3 from Theorem 3.1 and Lemma 3.3. Theorem 3.1, the ordered linear hypergraph girth Ramsey theorem, is introduced by 'The variant of the girth Ramsey theorem for ordered linear hypergraphs can be stated as follows' and is given without proof and without an explicit reference to the authors' preprint [10]; it is stronger than the graph version and Corollary 3.4(ii) uses it to control induced copies. This is a missing-support or black-box issue, not a circularity: Theorem 3.1 is not defined in terms of the paper's conclusions, no parameter is fitted to the target statements, and the new results are deductive consequences rather than repackagings of the input. No self-definitional, fitted-input-called-prediction, uniqueness-imported, ansatz-smuggled, or renaming pattern is present. The score 2 reflects the load-bearing unproven self-citation or omitted-reference concern without treating it as a circular reduction.
Assumptions & free parameters
assumptions (5)
- domain assumption Girth Ramsey theorem for graphs (Theorem 1.2)
- domain assumption Girth Ramsey theorem for ordered linear hypergraphs (Theorem 3.1)
- standard math de Bruijn-Erdos set mapping theorem (Theorem 2.1)
- domain assumption Rödl-Ruciński 2-density threshold results (used in Proposition 5.4)
- standard math Existence of a strictly 2-balanced subgraph F* with d2(F*) = m2(F)
Cite this review
Pith. "Pith review of Unavoidable subgraphs in Ramsey graphs." pith.science (2026). https://pith.science/paper/CAQMYG2E
@misc{pith2026250209830,
author = {Pith},
title = {Pith review of: Unavoidable subgraphs in Ramsey graphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/CAQMYG2E}},
note = {Machine review of arXiv:2502.09830}
}
abstract
We study subgraphs that appear in large Ramsey graphs for a given graph $F$. The recent girth Ramsey theorem of the first two authors asserts that there are Ramsey graphs such that all small subgraphs are `forests of copies of $F$' amalgamated on vertices and edges. We derive a few further consequences from this structural result and investigate to which extent such forests of copies must be present in Ramsey graphs.
Figures
Forward citations
Cited by 1 Pith paper
-
Off-Diagonal Ramsey Numbers for Linear Hypergraphs
For every k≥4 and C>1 there is a linear k-uniform hypergraph H with off-diagonal Ramsey number r(H,K_n^{(k)}) at least the (k-2)-fold tower of 2^{(log n)^C}.
Reference graph
Works this paper leans on
-
[10]
Chr. Reiher and V. Rödl,The girth Ramsey theorem, available at arXiv:2308.15589.Ò1.1
-
[1]
N. G. de Bruijn and P. Erdős,A colour problem for infinite graphs and a problem in the theory of relations, Indag. Math.13 (1951), 369–373. Nederl. Akad. Wetensch. Proc. Ser. A54. MR46630 Ò2.1
work page 1951
-
[2]
S. A. Burr, P. Erdős, and L. Lovasz,On graphs of Ramsey type, Ars Combin.1 (1976), no. 1, 167–190. MR419285 Ò1.3
work page 1976
- [3]
-
[4]
Erdős,Graph theory and probability, Canadian J
P. Erdős,Graph theory and probability, Canadian J. Math.11 (1959), 34–38, DOI10.4153/CJM-1959- 003-9. MR102081 Ò1
work page 1959
- [5]
-
[6]
Faudree,Ramsey minimal graphs for forests, Ars Combin.31 (1991), 117–124
R. Faudree,Ramsey minimal graphs for forests, Ars Combin.31 (1991), 117–124. MR1110225 Ò1.3
work page 1991
-
[7]
Łuczak,On Ramsey minimal graphs, Electron
T. Łuczak,On Ramsey minimal graphs, Electron. J. Combin.1 (1994), Research Paper 4, approx. 4, DOI10.37236/1184. MR1269165 Ò1.3
work page 1994
Show all 12 references
-
[8]
Nešetřil and V
J. Nešetřil and V. Rödl,Partitions of vertices, Comment. Math. Univ. Carolinae17 (1976), no. 1, 85–95. MR412044 Ò1
1976
-
[9]
, The structure of critical Ramsey graphs, Acta Math. Acad. Sci. Hungar.32 (1978), no. 3-4, 295–300, DOI10.1007/BF01902367. MR512405 Ò1.3
1978
-
[11]
Rödl and A
V. Rödl and A. Ruciński,Lower bounds on probability thresholds for Ramsey properties, Combinatorics, Paul Erdős is eighty, Vol. 1, Bolyai Soc. Math. Stud., János Bolyai Math. Soc., Budapest, 1993, pp. 317–346. MR1249720 Ò1.3, 5.1
1993
-
[12]
, Threshold functions for Ramsey properties, J. Amer. Math. Soc.8 (1995), no. 4, 917–942, DOI10.2307/2152833. MR1276825 Ò1.3 F achbereich Mathematik, Universität Hamburg, Hamburg, Germany Email address: christian.reiher@uni-hamburg.de Department of Mathematics, Emory Universit...
1995
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.