Coloring triangles in graphs

Ayush Basu; Marcelo Sales; Vojt\v{e}ch R\"odl

REVIEW 2 major objections 5 minor 22 references

Coloring triangles in graphs

T0 review · 2 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read The paper establishes the first quantitative upper bounds for the induced triangle Ramsey number $R_{\mathrm{ind}}^{\Delta}(F)$, including a tower-type bound for graphs whose triangles form a linear hypergraph.

desk verdict Two of the three main theorems rest on false inequalities, so the paper's headline bounds are unsupported; the definition and Proposition 1.3 are fine, but the main proofs need serious rework. read the letter →

arxiv 2411.13416 v1 pith:5SYM7LNU submitted 2024-11-20 math.CO

Ayush Basu , Vojtěch Rödl , Marcelo Sales This is my paper · ORCID

classification math.CO MSC 05C5505C6505D1005C80

keywords inducedRamseynumberstrianglecoloringshypergraphlinearhypergraphstighttreesweakregularityrandomgraphsmonochromaticcliques

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

For every graph $F$ there is a host graph $G$ such that any red/blue coloring of the triangles of $G$ contains an induced copy of $F$ whose triangles are all one color. This paper defines $R_{\mathrm{ind}}^{\Delta}(F)$, the smallest number of vertices of such a $G$, and proves the first numerical upper bounds for it in three natural settings. If $K_3(F)$, the 3-uniform hypergraph of triangles of $F$, is linear, the paper claims $R_{\mathrm{ind}}^{\Delta}(F) \le 2^{2^{240n}}$. If $F$ belongs to the family $B_n$---one part triangle-free, the other part independent, arbitrary cross edges---the bound is double exponential, $2^{2^{c n \log n}}$. If $K_3(F)$ is a tight tree, the bound is polynomial, $n^4$. These are the first concrete bounds for this Ramsey function, which previously was known only to be finite.

What carries the argument

The central object is the 3-uniform triangle hypergraph $K_3(F)$, whose edges are the vertex triples that form triangles in $F$; a suitable copy must be strongly induced, meaning that no hyperedge outside the copy contains any pair from the copy. The proofs build host graphs mostly from the random graph $G(N,1/2)$: a density property forces near-uniform edge densities on all large pairs; a greedy covering argument produces many monochromatic $K_n$ cliques; weak hypergraph regularization produces $(\varepsilon,d)$-dense tuples; and an embedding lemma for linear 3-graphs places a copy of $F$. For $B_n$, the construction is a blow-up of an induced Ramsey graph with added universal vertices, and for tight trees a minimal-subgraph argument keeps red-triangle degree high to permit greedy embedding.

What would settle it

In the proof of Lemma 3.3, compare the claimed bound $\ell = R_2(n-1)+1$ with the requirement $\ell \le \sqrt{(1/2)\log m}$ for $m = 2^{24n}$; since $R_2(n-1)$ grows exponentially while the threshold is $O(\sqrt{n})$, the chain of inequalities fails for $n \ge 2$, and the covering argument that selects $\ell$ vertices cannot run at that size. This calculation settles that the proof of Theorem 1.1, as written, does not establish the tower-type bound.

Watch

Extended reading notes

Core claim

The paper's central discovery is that the existence theorem $G \indarrow (F)^{\Delta}$ can be made quantitative for three families of $F$, and that the natural obstruction is the structure of the triangle hypergraph $K_3(F)$. The main theorem says that whenever $K_3(F)$ is linear---no two triangles share an edge---a host graph on $2^{2^{240n}}$ vertices suffices. For $F$ in $B_n$ the paper builds an explicit host graph from a blow-up of an induced Ramsey graph plus a layer of universal vertices, giving $2^{2^{c n \log n}}$. For tight trees it gives $n^4$. The proofs combine random graphs, weak hypergraph regularity, and embedding lemmas, and the paper notes the same strategy extends to colorings of $r$-cliques for $r \ge 3$.

Load-bearing premise

The tower-type bound depends on the assertion that the graph-Ramsey number $R_2(n-1)$ is less than $4n$, which is false for $n \ge 2$, so the step that forces many monochromatic $K_n$ cliques in the random host graph cannot be carried out at the stated size $m = 2^{24n}$.

Editorial extensions

If this is right

For every $n$-vertex graph $F$ with linear $K_3(F)$, there exists a host graph on $2^{2^{240n}}$ vertices such that every 2-coloring of its triangles contains a monochromatic induced copy of $F$.
For every $F$ in $B_n$, the same statement holds with $2^{2^{c n \log n}}$ vertices.
For every $F$ whose $K_3(F)$ is a tight tree, $n^4$ vertices suffice.
Because $R_{\mathrm{ind}}(F) \le R_{\mathrm{ind}}^{\Delta}(F)$, all three bounds transfer to ordinary induced Ramsey numbers for these families.

Reading between the lines

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

The double-exponential bound for $B_n$ and the polynomial bound for tight trees do not use Lemma 3.3, so they remain intact even if the tower-type proof needs repair.
A repair of Theorem 1.1 would likely replace the greedy clique-selection step by a different concentration argument or increase the parameter $m$, leaving the weak-regularity embedding pipeline unchanged.
The same three-step scheme suggests that the function $R_{\mathrm{ind}}^{K_r}(F)$ should admit bounds of tower height $r-1$, and that the tight-tree result may extend to any graph whose triangle hypergraph has bounded tree-depth.

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

Colleague,

This paper defines a natural Ramsey number R^Δ_ind(F) and gives three quantitative bounds. The definition itself is reasonable, and Proposition 1.3 (polynomial bound for tight trees) looks correct. But the two main theorems, 1.1 and 1.2, rest on concrete false inequalities, so the paper is not publishable in its current form.

The first problem is in Lemma 3.3, where the proof sets ℓ = R_2(n−1)+1 and asserts ℓ < 4n. That is false: the diagonal graph Ramsey number is exponential in n, so ℓ is far larger than 4n for n ≥ 14. The later bound ℓ ≤ sqrt((1/2) log m) is used to keep the shrinking set S_r above m^{1/2}; with the true ℓ the iteration cannot run. Theorem 1.1 depends on this lemma, so it is unsupported.

The second problem is in Theorem 1.2. The proof counts blue copies of F[A] and gets about (1/2)(N/m)^k, then tries to apply Erdős's extremal bound for K^{(k)}_{2,...,2}, which requires more than C N^{k−1/2^{k−1}} copies. Since N = m k 2^k, the count is smaller by roughly N^{1/2^{k−1}} than needed. The double-exponential upper bound therefore does not follow from the argument.

There is good material here: the weak-regularity framework and the embedding lemma in Appendix C are sensible, and the paper is clearly written. Proposition 1.3 appears sound, and the definition of R^Δ_ind is a natural object worth studying. But the two main theorems are the core of the paper, and their proofs contain load-bearing errors that are not minor typos.

I would not send this to peer review in its current state. A referee would quickly find the same failures. The authors need to rethink the proofs, especially the clique-construction in Lemma 3.3 and the counting in Theorem 1.2. If those are repaired, the paper could be a solid contribution. For now, it is not.

Referee Report

2 major / 5 minor

Summary. The paper defines the induced triangle Ramsey number R_ind^Δ(F), the smallest N such that some graph G on N vertices has the property that every 2-coloring of the triangles of G yields an induced copy of F whose triangles are all monochromatic. The main results are three quantitative upper bounds: a tower-type bound R_ind^Δ(F) ≤ 2^{2^{240 n}} when the triangle hypergraph K_3(F) is linear (Theorem 1.1), a double-exponential bound R_ind^Δ(F) ≤ 2^{2^{c n log n}} for graphs in the family B_n (Theorem 1.2), and a polynomial bound R_ind^Δ(F) ≤ n^4 when K_3(F) is a tight tree (Proposition 1.3). The proofs combine random graph properties, a weak hypergraph regularity lemma, and an embedding lemma for linear 3-graphs.

Significance. If the theorems are correct, they would provide the first explicit quantitative bounds for R_ind^Δ(F) for these natural families, including a polynomial bound in the tight-tree case. The paper builds a useful framework: Lemma 3.6 shows that a large random graph contains many monochromatic cliques with prescribed regularity, Lemma 4.2 gives a weak regularity lemma for n-partite n-uniform hypergraphs, and Lemma 4.3 is an embedding lemma for linear 3-graphs. Proposition 1.3's approach via average triangle degree is elegant and appears salvageable. However, the two main theorems currently rest on incorrect numerical estimates, so the central claims are not established as written.

major comments (2)

[§3.2, Lemma 3.3] The proof of Lemma 3.3 relies on the assertions ℓ = R_2(n−1)+1 < 4n and ℓ ≤ sqrt((1/2) log m). Since R_2(k) is the diagonal graph Ramsey number and R_2(k) ≥ 2^{k/2}, the inequality ℓ < 4n is false for all sufficiently large n; for instance, at n = 14, R_2(13) ≥ 91 while 4n = 56. More importantly, with the stated m = 2^{24n} (or any single-exponential m), sqrt((1/2) log m) is polynomial in n, whereas the true ℓ is exponential. The inductive construction requires |S_r| ≥ m^{1/2} to invoke property (3.3) at every step r < ℓ; once r reaches the true exponential value of ℓ, the bound |S_r| ≥ (1/2)^{r^2} m falls far below m^{1/2}. Consequently the auxiliary clique of size ℓ cannot be produced, and Corollary 3.4 and Lemma 3.6(A) are unsupported. To repair the proof, the authors need to replace this estimate with a correct upper bound on R_2(n−1) and choose m (and N) so that sqrt((1/2) log m) ≥ R_2(n−1)+1; the current numerical constants do not do this.
[§5, proof of Theorem 1.2] The counting argument for the number of distinct monochromatic copies of F[A] in the blow-up is incorrect. From |T| = N^m/(2 binom(m,k)) and the fact that each F[A]-copy is contained in at most N^{m-k} transversals, the number of distinct copies is at least N^k/(2 binom(m,k)) ≈ k! N^k/(2 m^k). With the stated choice N = m k^{2k}, this lower bound is ≈ k! k^{2k^2}/2, a constant depending only on k and n, not on N. Theorem 5.1 with t = 2 requires the number of copies to exceed C N^{k − 1/2^{k−1}}, which is enormous for the chosen N; the count is too small by a factor roughly N^{1/2^{k−1}} times a constant. The displayed lower bound in the manuscript does not follow from the preceding estimate. The construction needs a substantially larger N (e.g., N ≥ C m^{k 2^{k−1}} for a suitable constant C) for the extremal step to work, and this must be reconciled with the claimed final bound of 2^{2^{c n log n}}.

minor comments (5)

[§3.2, Lemma 3.3] The notation "m = 224n" is ambiguous; it should be clarified whether m denotes 2^{24n} or 2^{2^{4n}}. The subsequent inequalities depend on this distinction.
[§5, proof of Theorem 1.2] The displayed lower bound "≥ 1/2 (N/m)^k N^{k−1/2^{k−1}}" is not the expression obtained from the preceding line; it appears to be a typesetting or algebraic error.
[§6, proof of Proposition 1.3] Event (B) is stated for sets S with |S| ≥ n, but the proof applies it to sets with |S| ≤ n; the statement should read |S| ≤ n for the argument to be coherent.
[§4.2, Lemma 4.3] Condition (2) omits its subject: it should say that the triples (V_i, V_j, V_k) are (ε,d)-dense in H for every 1 ≤ i < j < k ≤ n.
[General] The manuscript contains several OCR-like artifacts that obscure the mathematics, for example "ei /integerdividetviu", "rmspkq", and "pε,d q-regular". A careful proofreading pass is needed before publication.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the target bounds are derived from external Ramsey theorems and included regularity/embedding lemmas, not from the bounds themselves.

full rationale

The paper's three upper bounds are proved by constructing explicit host graphs and invoking external results (Erdős–Rado, Erdős–Szekeres/Ramsey, Conlon–Fox–Sudakov, Kövári–Sós–Turán/Erdős) plus lemmas whose proofs are included in the appendix. There is no fitted parameter whose value is renamed as a prediction: constants such as the exponents in 2^{2^{240n}}, m=2^{24n}, and ε=2^{-216n} are fixed before the argument and are not calibrated to the target statements. The self-citations (e.g., [14], [20], with the present co-author Rödl) concern weak regularity and embedding tools; those lemmas are restated and proved in the paper, so the citations are not load-bearing as unverified premises. The only serious defect is a correctness error in Lemma 3.3: the assertion ℓ = R_2(n−1)+1 < 4n with ℓ ≤ sqrt((1/2)log m) is false because diagonal Ramsey numbers are exponential in n, and this invalidates the Erdős–Rado style iteration in the proof of Theorem 1.1. That is a mathematical error, not circularity: the theorem is not assumed, and no quantity is defined in terms of the quantity being bounded. Therefore the circularity score is 0.

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

No free parameters are fitted to data; all constants are chosen to satisfy inequalities in the proofs. The paper relies on standard mathematical background: Ramsey's theorem, Chernoff bounds, the Conlon-Fox-Sudakov induced Ramsey bound, Erdős's extremal theorem for complete k-partite k-graphs, and weak hypergraph regularity. No new entities are invented. The main risk is not circularity but the incorrect use of these background results in the two main proofs.

assumptions (6)

standard math Ramsey's theorem and the Erdős-Szekeres bound R_2(k) ≤ 4^k
Invoked in Lemma 3.3 to assert K_{ℓ−1} → (K_{n−1})^2; the paper misapplies it by claiming R_2(n−1)+1 < 4n.
standard math Chernoff bounds for binomial random variables
Used in Lemma 3.2 and Proposition 1.3 to establish density concentration in random graphs.
standard math Conlon-Fox-Sudakov induced Ramsey theorem: R_ind(F) ≤ 2^{c n log n}
Used in Theorem 1.2 to construct the base graph H.
standard math Erdős extremal theorem ex(N, K^{(k)}_{t,...,t}) ≤ C N^{k−1/t^{k−1}}
Used in Theorem 1.2 to find a blue blow-up; the count of blue copies appears insufficient for the stated N.
standard math Weak hypergraph regularity lemma and linear hypergraph embedding lemma
Stated as Lemmas 4.2 and 4.3 in the paper and used in Theorem 1.1.
domain assumption Random graph events (A) and (B) hold with high probability
Proved via Chernoff and union bound in Proposition 1.3; the statement of (B) has a likely typo in the bound on |S|.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Coloring triangles in graphs." pith.science (2026). https://pith.science/paper/5SYM7LNU

@misc{pith2026241113416,
  author       = {Pith},
  title        = {Pith review of: Coloring triangles in graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5SYM7LNU}},
  note         = {Machine review of arXiv:2411.13416}
}

abstract

We study quantitative aspects of the following fact: For every graph $F$, there exists a graph $G$ with the property that any $2$-coloring of the triangles of $G$ yields an induced copy of $F$, in which all triangles are monochromatic. We define the Ramsey number $R_{\text{ind}}^{\Delta}(F)$ as the smallest size of such a graph $G$. Although this fact has several proofs, all of them provide tower-type bounds. We study the number $R_{\text{ind}}^{\Delta}(F)$ for some particular classes of graphs $F$.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

22 extracted references · 22 canonical work pages

[1]

F. G. Abramson and L. A. Harrington, Models without indiscernibles , J. Symbolic Logic 43 (1978), no. 3, 572–600. MR 503795 Ò1

work page 1978
[2]

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

J. Beck, On size Ramsey number of paths, trees and circuits. II , Mathematics of Ramsey theory, 1990, pp. 34–45. MR 1083592 Ò6

work page 1990
[3]

Bhat and V

V. Bhat and V. Rödl, A short proof of the induced Ramsey theorem for hypergraphs , Discrete Math. 339 (2016), no. 3, 1147–1149. MR 3433919 Ò1

work page 2016
[4]

Conlon, D

D. Conlon, D. Dellamonica, S. La Fleur, V. Rödl, and M. Sch acht, A note on induced Ramsey numbers , A journey through discrete mathematics, 2017, pp. 357–366. MR3726604 Ò1

work page 2017
[5]

Conlon, J

D. Conlon, J. Fox, and B. Sudakov, On two problems in graph Ramsey theory , Combinatorica 32 (2012), no. 5, 513–535. MR 3004807 Ò1

work page 2012
[6]

Deuber, Generalizations of Ramsey’s theorem , Inﬁnite and ﬁnite sets (Colloq., Keszthely, 1973; dedicated to P

W. Deuber, Generalizations of Ramsey’s theorem , Inﬁnite and ﬁnite sets (Colloq., Keszthely, 1973; dedicated to P. Erdos on his 60th birthday), Vols. I, II, III, 1975, pp. 323–332. MR 369127 Ò1

work page 1973
[7]

Deuber, Partitionstheoreme für Graphen , Comment

W. Deuber, Partitionstheoreme für Graphen , Comment. Math. Helv. 50 (1975), no. 3, 311–320. MR401546 Ò1, 7

work page 1975
[8]

Erd˝ os and R

P. Erd˝ os and R. Rado, Combinatorial theorems on classiﬁcations of subsets of a gi ven set , Proc. London Math. Soc. (3) 2 (1952), 417–439. MR 65615 Ò3.2

work page 1952

Show all 22 references

[9]

Erdős, On extremal problems of graphs and generalized graphs , Israel J

P. Erdős, On extremal problems of graphs and generalized graphs , Israel J. Math. 2 (1964), 183–190. MR183654 Ò5.1

1964
[10]

Erdős, A

P. Erdős, A. Hajnal, and L. Pósa, Strong embeddings of graphs into colored graphs , Inﬁnite and ﬁnite sets (Colloq., Keszthely, 1973; dedicated to p. erdos on his 60th birthday), Vols. I, II, III, 1975, pp. 585–595. MR 382049 Ò1

1973
[11]

Erdős and G

P. Erdős and G. Szekeres, A combinatorial problem in geometry , Compositio Math. 2 (1935), 463–470. MR1556929 Ò1

1935
[12]

Erdős, On some problems in graph theory, combinatorial analysis an d combinatorial number theory, Graph theory and combinatorics (Cambridge, 1983), 1984, pp

P. Erdős, On some problems in graph theory, combinatorial analysis an d combinatorial number theory, Graph theory and combinatorics (Cambridge, 1983), 1984, pp . 1–17. MR 777160 Ò1

1983
[13]

Kohayakawa, H

Y. Kohayakawa, H. J. Prömel, and V. Rödl, Induced Ramsey numbers , Combinatorica 18 (1998), no. 3, 373–404. MR 1721950 Ò1

1998
[14]

Kohayakawa, B

Y. Kohayakawa, B. Nagle, V. Rödl, and M. Schacht, Weak hypergraph regularity and linear hyper- graphs, J. Combin. Theory Ser. B 100 (2010), no. 2, 151–160. MR 2595699 Ò4.2, C

2010
[15]

Komlós, A

J. Komlós, A. Shokoufandeh, M. Simonovits, and E. Szeme rédi, The regularity lemma and its appli- cations in graph theory , Theoretical aspects of computer science (Tehran, 2000), 2 002, pp. 84–112. MR1966181 ÒC

2000
[16]

Kövari, V

T. Kövari, V. T. Sós, and P. Turán, On a problem of K. Zarankiewicz , Colloq. Math. 3 (1954), 50–57. MR65617 Ò5

1954
[17]

Nešetřil and V

J. Nešetřil and V. Rödl, Partitions of subgraphs , Recent advances in graph theory (Proc. Second Czechoslovak Sympos., Prague, 1974), 1975, pp. 413–423. MR 429655 Ò1, 7

1974
[18]

Nešetřil and V

J. Nešetřil and V. Rödl, Partitions of ﬁnite relational and set systems , J. Combinatorial Theory Ser. A 22 (1977), no. 3, 289–312. MR 437351 Ò1

1977
[19]

, Two proofs of the Ramsey property of the class of ﬁnite hyperg raphs, European J. Combin. 3 (1982), no. 4, 347–352. MR 687733 Ò1

1982
[20]

Y. Peng, V. Rödl, and A. Ruciński, Holes in graphs , Electron. J. Combin. 9 (2002), no. 1, Research Paper 1, 18. MR 1887082 Ò4.1

2002
[21]

F. P. Ramsey, On a Problem of Formal Logic , Proc. London Math. Soc. (2) 30 (1929), no. 4, 264–286. MR1576401 Ò1 18 AYUSH BASU, VOJTĚCH RÖDL, AND MARCELO SALES

1929
[22]

Rödl, The dimension of a graph and generalized ramsey theorems , Master’s thesis, 1973

V. Rödl, The dimension of a graph and generalized ramsey theorems , Master’s thesis, 1973. Ò 1 §Appendix A. Proof of Lemma 3.2 Proof. LetGpt, 1{2q be the random graph with vertex set V of sizet. We ﬁrst show that for every pair of subsets of size X andY such that X andY are di...

1973

Pith tools

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

[1] [1]

F. G. Abramson and L. A. Harrington, Models without indiscernibles , J. Symbolic Logic 43 (1978), no. 3, 572–600. MR 503795 Ò1

work page 1978

[2] [2]

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

J. Beck, On size Ramsey number of paths, trees and circuits. II , Mathematics of Ramsey theory, 1990, pp. 34–45. MR 1083592 Ò6

work page 1990

[3] [3]

Bhat and V

V. Bhat and V. Rödl, A short proof of the induced Ramsey theorem for hypergraphs , Discrete Math. 339 (2016), no. 3, 1147–1149. MR 3433919 Ò1

work page 2016

[4] [4]

Conlon, D

D. Conlon, D. Dellamonica, S. La Fleur, V. Rödl, and M. Sch acht, A note on induced Ramsey numbers , A journey through discrete mathematics, 2017, pp. 357–366. MR3726604 Ò1

work page 2017

[5] [5]

Conlon, J

D. Conlon, J. Fox, and B. Sudakov, On two problems in graph Ramsey theory , Combinatorica 32 (2012), no. 5, 513–535. MR 3004807 Ò1

work page 2012

[6] [6]

Deuber, Generalizations of Ramsey’s theorem , Inﬁnite and ﬁnite sets (Colloq., Keszthely, 1973; dedicated to P

W. Deuber, Generalizations of Ramsey’s theorem , Inﬁnite and ﬁnite sets (Colloq., Keszthely, 1973; dedicated to P. Erdos on his 60th birthday), Vols. I, II, III, 1975, pp. 323–332. MR 369127 Ò1

work page 1973

[7] [7]

Deuber, Partitionstheoreme für Graphen , Comment

W. Deuber, Partitionstheoreme für Graphen , Comment. Math. Helv. 50 (1975), no. 3, 311–320. MR401546 Ò1, 7

work page 1975

[8] [8]

Erd˝ os and R

P. Erd˝ os and R. Rado, Combinatorial theorems on classiﬁcations of subsets of a gi ven set , Proc. London Math. Soc. (3) 2 (1952), 417–439. MR 65615 Ò3.2

work page 1952