Pith. sign in

REVIEW 1 major objections 5 minor 22 references

Large monochromatic components in 3-edge-colored Steiner triple systems

T0 review · 1 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read This paper proves that a randomly chosen Steiner triple system almost surely has a monochromatic component on at least $n - 2n^{1-\delta}$ vertices in every 3-edge-coloring, for some absolute $\delta > 0$.

desk verdict Main theorem is solid and novel, but the proof of Theorem 4.2 in Section 4 is invalid—repair or remove it. read the letter →

arxiv 1908.00837 v3 pith:CBTNOKMZ submitted 2019-08-02 math.CO

Louis DeBiasio , Michael Tait This is my paper · ORCID
classification math.CO MSC 05B0705C1505C6505D1005D40
keywords Steinertriplesystemsmonochromaticcomponentsedge-colorings3-partiteholerandomRamseytheoryhypergraphsindependencenumber
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

The paper asks a Ramsey-type question: in any 3-coloring of the edges of a Steiner triple system on $n$ vertices, how large a monochromatic component is unavoidable? Its main result is that for almost all Steiner triple systems the answer is nearly $n$: there is an absolute constant $\delta>0$ such that a uniformly random system has $mc_3(S) \ge n - 2n^{1-\delta}$ with probability tending to 1. The proof routes everything through the 3-partite hole number $\alpha^*_3(S)$ — the largest size of three disjoint equal vertex sets that no edge meets all three — and shows first that every system satisfies $mc_3(S) \ge n - 2\alpha^*_3(S)$, then that random systems almost surely have $\alpha^*_3(S) \le n^{1-\delta}$. A reader should care because it shows the classical worst-case guarantee of about $2n/3$ is atypical: the obstruction to large monochromatic components is precisely the presence of large cross-free sets, and typical systems do not have them.

What carries the argument

The load-bearing object is the 3-partite hole number $\alpha^*_3(H)$: the largest $a$ for which there exist disjoint sets $X_1,X_2,X_3 \subseteq V(H)$, each of size $a$, with no edge of $H$ intersecting all three. It appears on both sides of the inequality. A hole gives an explicit 3-coloring with no monochromatic component larger than $n-a$, which is Proposition 1.1. Conversely, the proof of Theorem 2.3 takes an arbitrary 3-coloring, records the colors of pairs in the shadow graph, and applies a lemma about 3-multicolorings of complete graphs; that lemma yields either a spanning monochromatic component, a four-part structure with the two larger parts forming a component, or a four-part structure with three components, and in each case counting edges against the hole number gives $mc_3(H) \ge n - 2\alpha^*_3(H)$. The probabilistic half is carried by a Lipschitz concentration bound: the number of edges crossing three fixed sets of size $n^{1-\delta}$ in the random partial system is concentrated around $c n^{2-3\delta}$, so the union bound forces at least one cross-edge between every triple of such sets, implying $\alpha^*_3 \le n^{1-\delta}$. A transfer theorem supplied by [19] converts this event from the sparse random process to the uniform distribution over Steiner triple systems.

What would settle it

For infinitely many $n \equiv 1,3 \pmod 6$, sample a uniformly random Steiner triple system $S$ and check whether three disjoint sets of size $n^{1-\delta}$ can avoid all cross-edges: if this happens with probability bounded below by a positive constant for some fixed $\delta>0$, then the claimed almost-sure bound $\alpha^*_3(S) \le n^{1-\delta}$, and with it Theorem 1.4, is false.

Watch

Extended reading notes

Core claim

On the paper's own terms, the discovery is a two-sided relationship between guaranteed monochromatic components and cross-free sets. For every 3-uniform hypergraph in which every pair of vertices lies in an edge, the paper proves a dichotomy (Theorem 2.3): either $mc_3(S) \ge n - \alpha^*_3(S)$, or the coloring and the vertex set have a rigid four-part structure in which the three smaller parts have size at most $\alpha^*_3(S)$, and in either case $mc_3(S) \ge n - 2\alpha^*_3(S)$. Since the trivial upper bound $mc_3(S) \le n - \alpha^*_3(S)$ holds for every system, this pins the guaranteed component size to the size of the largest 3-partite hole, up to a factor of 2 and a structural exceptional case. The probabilistic half shows that for a uniformly random Steiner triple system, $\alpha^*_3(S) \le n^{1-\delta}$ almost surely; the argument counts edges crossing three fixed large sets in a sparse random partial system, applies a Lipschitz concentration inequality, and transfers the high-probability statement to the uniform distribution on Steiner triple systems. The stated consequence is Theorem 1.4: almost all Steiner triple systems have $mc_3(S) = (1-o(1))n$.

Load-bearing premise

The load-bearing premise is that a property of sparse random partial Steiner triple systems holding with probability at least $1-\exp(-n^{2-b})$ also holds almost surely in a uniformly random Steiner triple system; if that transfer statement does not apply exactly to the cross-edge property used here, the bound $\alpha^*_3(S) \le n^{1-\delta}$ and hence the main theorem would not follow.

Editorial extensions

If this is right

  • If the main theorem is right, the worst-case behavior identified by the earlier bound $(2n+3)/3$ is realized only on a sparse family of Steiner triple systems; a typical system behaves like the complete 3-uniform hypergraph, where a spanning monochromatic component is forced.
  • Combining Theorem 1.3 with the universal upper bound $mc_3(S) \le n - \alpha^*_3(S) \le n - c\sqrt{n\log n}$ leaves a gap: for random systems the lower bound is $n - 2n^{1-\delta}$, and a natural target is $n - O(\sqrt{n\log n})$.
  • For binomial random 3-uniform hypergraphs with $p > c\log n/n$, the same dichotomy gives $mc_3(H_3(n,p)) \ge n - 2(3\log n/p)^{1/2}$ almost surely, complementing the known upper bound from the independence number.
  • An infinite family of bicolorable Steiner triple systems shows the general lower bound $2n/3+1$ is tight up to lower-order terms, so the typical and worst cases are separated.

Reading between the lines

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

  • Inference: If the open problem $\alpha^*_3(S) = O(\sqrt{n\log n})$ a.a.s. were settled, the same proof would immediately upgrade the main theorem to $mc_3(S) \ge n - O(\sqrt{n\log n})$ a.a.s., matching the universal upper bound up to the constant.
  • Inference: Theorem 2.3's exceptional four-part structure suggests that random Steiner triple systems may actually satisfy the stronger equality $mc_3(S) = n - \alpha^*_3(S)$ a.a.s., since the exceptional structure requires a very rigid partition; searching for that partition in random systems is a concrete next step.
  • Inference: The concentration estimate used here for $\alpha^*_3$ may generalize to holes with more than three parts or to $r$-colorings, where the obstacle is a multi-color analogue of the complete-graph lemma; the paper raises this as a problem but does not resolve it.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

1 major / 5 minor

Summary. The paper studies the largest monochromatic component in 3-edge-colorings of Steiner triple systems. It proves that for every Steiner triple system S, mc3(S) ≥ n − 2α*_3(S) (Theorem 1.3), where α*_3 is the 3-partite-hole number. It then shows that for a uniformly random S ∈ S_n, a.a.s. α*_3(S) ≤ n^{1−δ} for some absolute δ > 0, and hence mc3(S) ≥ n − 2n^{1−δ} (Theorem 1.4); this is obtained by applying Kwan's transfer theorems to a concentration bound for the random partial Steiner triple system G*(n, 1/(2n)). The paper also gives an upper bound for all Steiner triple systems of the form n − Ω(√(n log n)), an infinite family of systems for which mc3 is asymptotically 2n/3 (Section 5), bounds for Bose and Skolem systems, and several open problems. The proof of Theorem 4.2 (Gyárfás's absolute lower bound 2n/3 + 1) in Section 4 contains a serious error, although this theorem is known and is not used in the proof of Theorem 1.4.

Significance. The main result, if valid, is genuinely interesting: it shows that the typical Steiner triple system behaves very differently from the worst case, with guaranteed monochromatic components covering all but n^{1−δ} vertices in every 3-edge-coloring. Theorem 1.3 is a clean and useful reduction of the component problem to the 3-partite-hole parameter, and the proof of Theorem 3.1 is a well-executed combination of a union bound, a Lipschitz concentration inequality, and Kwan's random-process transfer; I found no gap in that chain. The paper is generous and accurate in attributing prior results, and the arguments are deductive with no fitted parameters. These strengths would normally make the paper acceptable, but the false proof of Theorem 4.2 in Section 4 must be corrected before publication; because that theorem is independent of the main line, the central contribution is not threatened.

major comments (1)
  1. [Section 4] In the proof of Theorem 4.2, after introducing the relaxed program, the paper asserts: "Then we have x1 ≥ n − 3x2 and so n(n−1)/6 ≤ C(n−3x2,2)+3C(x2,2)." This implication is backwards. The constraints n(n−1)/6 ≤ C(x1,2)+3C(x2,2) and x1 ≥ n−3x2 imply n(n−1)/6 ≤ C(x1,2)+3C(x2,2) and C(x1,2) ≥ C(n−3x2,2); the latter quantity is a lower bound on the feasible left-hand side, not an upper bound, so the displayed inequality need not hold. Indeed, for n=27 the pair (x1,x2)=(11,7) is feasible for the relaxed program: x1+3x2=32≥27, x1≥x2, and C(11,2)+3C(7,2)=118≥117, yet z2=18 < (2n+1)/3 = 18.33. Thus the claimed minimum of the relaxed program is false and the proof of Theorem 4.2 collapses at this step. Since Theorem 4.2 is a known result of Gyárfás and is not used in the proof of Theorem 1.4, the central claim of the paper survives, but the proof should be repaired or replaced by a citation.
minor comments (5)
  1. [Section 3] Page 6: "for all sufficiently large n ≡ 1, 3 mod n" should read "mod 6".
  2. [Lemma 5.3 and Section 7] The proof of Lemma 5.3 and the concluding discussion in Section 7 refer to "Theorem 1.1", but the statement used is Proposition 1.1; please correct the cross-references.
  3. [Section 3] The sentence "for all n ≡ 1, 3 mod 6, there exists S ∈ S_n with α*_3(S) ≥ 2⌊n/9⌋ (see Section 6)" is not backed up by Section 6, which contains no such construction; either add the argument or give a precise reference.
  4. [Proposition 1.1] The coloring rule "color every edge which avoids Xi with color i for all i" can assign several colors to one edge; specify that each edge is assigned one color among the colors it avoids.
  5. [Section 3] The proof of Theorem 3.1 uses sets A, B, C of size n^{1−δ}, which need not be integral; state a rounding convention or use ⌊n^{1−δ}⌋ throughout.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity; the main theorem is derived from external transfer theorems and a fully reproduced structural lemma, with no fitted inputs or self-referential predictions.

full rationale

The paper's central claim, Theorem 1.4, is derived as Theorem 1.3 plus Theorem 3.1. Theorem 3.1 is proved by applying Kwan's transfer theorems (Theorems 3.3 and 3.4) and Warnke's concentration inequality (Lemma 3.5) to a monotone property in the random partial Steiner system G*(n, 1/(2n)). These are independent external tools, not results of the present authors, and the probability threshold required by Kwan's theorem is checked explicitly by a union bound and a Lipschitz calculation. The only self-citation is Lemma 2.2, taken from a paper co-authored by DeBiasio, but it is stated and proved in full in this manuscript and is a structural lemma about 3-multicolorings of complete graphs; it does not encode the target parameter mc3(S) or alpha*_3(S). No parameter is fitted to data and no predicted quantity is redefined from an input. Gyárfás's earlier results are used as benchmarks and comparisons, not as load-bearing inputs. The known issue in Section 4 concerns the correctness of a convexity optimization argument in the proof of Theorem 4.2, which is a mathematical-error concern rather than a circularity concern and does not affect the main almost-all result.

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

The paper introduces no free parameters, fitted constants, or new entities. It relies on standard combinatorial background and on several external theorems (Kwan, Warnke, DeBiasio-McKenney). The central claim is a pure existence and almost-sure statement.

assumptions (5)
  • standard math Existence of Steiner triple systems on n vertices exactly when n ≡ 1, 3 mod 6.
    Background fact stated in Section 1 and used throughout; the results are formulated only for such n.
  • domain assumption Kwan's transfer theorem (Theorem 3.3, [19, Theorem 2.4]): a property holding with probability at least 1 - exp(-n^(2-b)) in the triangle removal process also holds with high probability in a uniformly random Steiner triple system.
    Used in Section 3 to transfer the discrepancy bound from G*(n, 1/(2n)) to a uniformly random Steiner triple system. This is an external theorem not proved in the paper.
  • domain assumption Kwan's comparison lemma (Theorem 3.4, [19, Lemma 2.10]): for monotone increasing properties, the triangle removal process and G*(n, 1/(2n)) have comparable probabilities.
    Used in Section 3 to relate the triangle removal process to G*(n, 1/(2n)). External to this paper.
  • standard math Lemma 2.2 from [8] (DeBiasio-McKenney): structural dichotomy for 3-multicolorings of complete graphs.
    Used as the main structural tool in Theorem 2.3. The lemma is published and its proof is reproduced in the paper, so it is not an unstated assumption.
  • standard math Warnke's concentration inequality (Lemma 3.5, [22, Theorem 1.3]) for Lipschitz functions of independent Bernoulli variables.
    Used in the proof of Theorem 3.1 to show concentration of the edge count e*(A,B,C). External published result.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Large monochromatic components in 3-edge-colored Steiner triple systems." pith.science (2026). https://pith.science/paper/CBTNOKMZ

@misc{pith2026190800837,
  author       = {Pith},
  title        = {Pith review of: Large monochromatic components in 3-edge-colored Steiner triple systems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CBTNOKMZ}},
  note         = {Machine review of arXiv:1908.00837}
}
abstract

It is known that in any $r$-coloring of the edges of a complete $r$-uniform hypergraph, there exists a spanning monochromatic component. Given a Steiner triple system on $n$ vertices, what is the largest monochromatic component one can guarantee in an arbitrary 3-coloring of the edges? Gy\'arf\'as proved that $(2n+3)/3$ is an absolute lower bound and that this lower bound is best possible for infinitely many $n$. On the other hand, we prove that for almost all Steiner triple systems the lower bound is actually $(1-o(1))n$. We obtain this result as a consequence of a more general theorem which shows that the lower bound depends on the size of a largest \emph{3-partite hole} (that is, sets $X_1, X_2, X_3$ with $|X_1|=|X_2|=|X_3|$ such that no edge intersects all of $X_1, X_2, X_3$) in the Steiner triple system (Gy\'arf\'as previously observed that the upper bound depends on this parameter). Furthermore, we show that this lower bound is tight unless the coloring has a particular structure. We also suggest a variety of other Ramsey problems in the setting of Steiner triple systems.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

22 extracted references · 22 canonical work pages

  1. [1]

    Alon and P

    N. Alon and P. Frankl. Families in which disjoint sets hav e large union. Annals of the New York Academy of Sciences 555, no. 1 (1989), 9–16

    work page 1989

  2. [2]

    N. Alon, P. Frankl, and L. Lov´ asz. The chromatic number o f Kneser hypergraphs. Transactions of the American Mathematical Society 298, no. 1 (1986), 359–370

    work page 1986

  3. [3]

    Bennett, L

    P. Bennett, L. DeBiasio, A. Dudek, and S. English. Large m onochromatic compo- nents and long monochromatic cycles in random hypergraphs. European Journal of Combinatorics 76 (2019), 123–137

    work page 2019

  4. [4]

    Spreading linear triple systems and expander triple systems

    Z. Bl´ azsik and Z. Nagy, Spreading linear triple systems and expander triple systems, arXiv:1906.03149

    work page Pith review arXiv 1906

  5. [5]

    C. J. Colbourn, J. H. Dinitz, and A. Rosa. Bicoloring Stei ner triple systems. The Electronic Journal of Combinatorics 6, no. 1 (1999), P.25

    work page 1999

  6. [6]

    Colbourn and A

    C.J. Colbourn and A. Rosa. Triple systems. Oxford University Press , 1999

    work page 1999

  7. [7]

    R. Duke, H. Lefmann and V. R¨ odl. On uncrowded hypergraph s. Random Structures and Algorithms 6, (1995), 209–212

    work page 1995

  8. [8]

    DeBiasio, P

    L. DeBiasio, P. McKenney. Density of monochromatic infin ite subgraphs. Combina- torica, (2019). https://doi.org/10.1007/s00493-018-3724-2

    work page doi:10.1007/s00493-018-3724-2 2019

Show all 22 references
  1. [9]

    Eustis and J

    A. Eustis and J. Verstra¨ ete. On the independence number of Steiner systems. Combi- natorics, Probability and Computing 22, no. 2 (2013), 241–252

    2013

  2. [10]

    Ferber and M

    A. Ferber and M. Kwan, Almost all Steiner triple systems are almost resolvable, arXiv:1907.06744

    1907 arXiv

  3. [11]

    F¨ uredi and A

    Z. F¨ uredi and A. Gy´ arf´ as. Coveringt-element sets by partitions. European Journal of Combinatorics 12 , no. 6 (1991), 483–489

    1991

  4. [12]

    Grable, K

    D.A. Grable, K. T. Phelps, and V. R¨ odl. The minimum inde pendence number for designs. Combinatorica 15, no. 2 (1995), 175–185

    1995

  5. [13]

    Gy´ arf´ as

    A. Gy´ arf´ as. Partici´ ofed´ esek ´ es lefog´ ohalmazokhipergr´ afokban, Tanulm´ anyok-MTA Sz´ amit´ astechn. Automat. Kutat´ o Int. Budapest62, (1977)

    1977

  6. [14]

    Gy´ arf´ as

    A. Gy´ arf´ as. Large cross-free sets in Steiner triple systems. Journal of Combinatorial Designs 23, no. 8 (2015), 321–327

    2015

  7. [15]

    Gy´ arf´ as and P

    A. Gy´ arf´ as and P. Haxell. Large monochromatic components in colorings of complete 3-uniform hypergraphs. Discrete Mathematics 309, no. 10 (2009), 3156–3160

    2009

  8. [16]

    P. E. Haxell, T. /suppress Luczak, Y. Peng, V. R¨ odl, A. Ruci´ nski, M. Simonovits, and J. Skokan. The Ramsey number for hypergraph cycles I. Journal of Combinatorial Theory, Series A 113, no. 1 (2006), 67–83. 16

    2006

  9. [17]

    Kostochka, D

    A. Kostochka, D. Mubayi, and J. Verstra¨ ete. On indepen dent sets in hypergraphs. Random Structures & Algorithms 44, no. 2 (2014), 224–239

    2014

  10. [18]

    Krivelevich and B

    M. Krivelevich and B. Sudakov. The chromatic numbers of random hypergraphs. Random Structures & Algorithms 12, no. 4 (1998), 381–403

    1998

  11. [19]

    M. Kwan. Almost all Steiner triple systems have perfect matchings. arXiv preprint arXiv:1611.02246 (2016)

    2016 arXiv

  12. [20]

    Linial and Z

    N. Linial and Z. Luria. Discrepancy of high-dimensiona l permutations, Discrete Anal- ysis 2016:11, 8pp

    2016

  13. [21]

    K. T. Phelps and V. R¨ odl. Steiner triple systems with minimum independence num- ber. Ars Combin. 21 (1986), 167–172

    1986

  14. [22]

    L. Warnke. On the method of typical bounded differences. Combinatorics, Probability and Computing 25, no. 2 (2016), 269–299. 17

    2016

Pith tools

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