{"id":"979aed9c-c2f8-428b-af15-7c0b7ad8db18","arxiv_id":"1908.00837","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For almost all Steiner triple systems on n vertices, every 3-edge-coloring has a monochromatic component on (1-o(1))n vertices.","lead":"This paper proves that almost every Steiner triple system has a near-spanning monochromatic component under any 3-coloring of its edges, improving the known worst-case bound of about 2n/3. It also links the exact answer to a new '3-partite hole' parameter of the design.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1.4's proof is sound; the genuine flaw is Section 4's proof of Theorem 4.2, which should be repaired.","rationale":"The reader's conditional verdict is correct, but their named weakest assumption is not the real weak spot. I checked the transfer-theorem step in detail: the monotone property P is appropriate, the 3-Lipschitz constant for f_{A,B,C} is valid because G* is linear, and with delta < b/6 the union bound over 2^{3n} choices is dominated by exp(-Omega(n^{2-6delta})). So Theorem 1.4's proof appears sound. The genuine flaw is the Section 4 integer-program proof of Theorem 4.2: the step from x1 >= n-3x2 to the quadratic inequality has the wrong direction, and a concrete n=27 feasible point shows the relaxed minimum is far below the claimed value. Because Theorem 4.2 is a known result not used in proving Theorem 1.4, this does not undermine the central claim, but it is a real internal inconsistency that justifies a conditional rather than unconditional acceptance. The reader also identified the Section 4 flaw in their rationale, so my verdict agrees with theirs even though my diagnosis of the weakest assumption differs.","tokens_in":15525,"tokens_out":31084,"duration_ms":305568,"concrete_test":"Verify the n=27 arithmetic: in the relaxed program of Section 4, check that (x1,x2)=(11,7) satisfies all constraints, giving objective 18 below (2n+1)/3. Alternatively, run an integer LP solver on the relaxed program and observe the minimum z2 is 17, not > (2n+1)/3. Then confirm that the original unrelaxed program still gives z1=19 for n=27, so the intended bound is true but the relaxation is too weak. This settles that the Section 4 proof is invalid as written.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim (Theorem 1.4) is not threatened: the Kwan transfer application checks out, and the 3-Lipschitz step is justified because G* is a partial Steiner system, so altering one input triple can change the count of crossing edges by at most O(1) (it can add the new triple or delete one edge per pair). The real problem is the proof of Theorem 4.2 in Section 4. After relaxing to z2, the authors write 'x1 >= n - 3x2 and so n(n-1)/6 <= C(n-3x2,2)+3C(x2,2)'. This is a direction error: the edge constraint is a lower bound on C(x1,2)+3C(x2,2), and reducing x1 to n-3x2 only makes the RHS smaller, so the inequality need not hold. Indeed, for n=27 the relaxed program has the feasible point (x1,x2)=(11,7): x1+3x2=32>=27, x1>=x2, and C(11,2)+3C(7,2)=55+63=118>=117, with z2=18 < (2n+1)/3=18.333. Thus the claimed relaxed minimum is false and the presented proof of Theorem 4.2 is invalid. Since Theorem 4.2 is a known result of Gyárfás and is not used in the proof of Theorem 1.4, the main contribution survives, but the manuscript must repair or remove this proof.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":15744,"tokens_out":25798,"duration_ms":235070,"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":[{"comment":"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.","section":"Section 4"}],"minor_comments":[{"comment":"Page 6: \"for all sufficiently large n ≡ 1, 3 mod n\" should read \"mod 6\".","section":"Section 3"},{"comment":"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.","section":"Lemma 5.3 and Section 7"},{"comment":"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.","section":"Section 3"},{"comment":"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.","section":"Proposition 1.1"},{"comment":"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.","section":"Section 3"}],"recommendation":"major_revision","confidential_remarks":"The main theorem is sound in my reading, so I do not regard this as a reject; the Section 4 error is localized and can be fixed by deferring to Gyárfás. Please also ask the authors to supply the missing justification for the α*_3 lower-bound assertion attributed to Section 6."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear [Colleague],\n\nThe headline is that the main theorem is real: for almost all Steiner triple systems S, mc3(S) = (1-o(1))n, and the proof via alpha*_3(S) is coherent. The paper's one genuine flaw is the proof of Theorem 4.2 in Section 4; the relaxed integer program argument has a direction error and does not prove what it claims. That theorem is a known result of Gyárfás and is not used in the proof of Theorem 1.4, so the main contribution stands, but the section needs repair.\n\nWhat is actually new: Theorem 1.4 answers a natural Ramsey question for random designs. The general inequality mc3(H) >= n - 2alpha*_3(H) for 3-uniform hypergraphs with delta2(H)>=1 (Theorem 2.3) is a useful structural result, and the proof—via a complete-graph multicoloring lemma from DeBiasio-McKenney, reproduced here—is clean. Theorem 3.1, showing alpha*_3(S) <= n^{1-delta} a.a.s., is a solid concentration argument (Warnke’s inequality, union bound) and the application of Kwan’s transfer theorems checks out. The paper also answers Gyárfás’s problem on the gap between min and max alpha*_3, and Section 5 supplies a proof—previously missing in the literature—that the absolute lower bound is asymptotically tight for an infinite family. That is genuine credit.\n\nThe soft spot is Section 4. The authors relax the natural integer program and claim z2 > (2n+1)/3, but the inequality n(n-1)/6 <= C(n-3x2,2)+3C(x2,2) is not implied: the edge constraint is a lower bound on C(x1,2)+3C(x2,2), and replacing x1 by n-3x2 only shrinks the RHS. Indeed, for n=27 the point (x1,x2)=(11,7) is feasible for the relaxed program with z2=18 < 18.333, so the claimed minimum is false. The proof should either be replaced with a citation to Gyárfás’s original argument or repaired with a correct IP analysis. Minor: the \"n ≡ 1, 3 mod n\" in the introduction is a typo for mod 6.\n\nCitation pattern is fine: Lemma 2.2 is reproved and not load-bearing in a circular way; Kwan’s theorems are external and used correctly.\n\nBottom line: send this to a referee. The main theorem is worth refereeing; the Section 4 issue is localized and fixable. I’d recommend conditional acceptance after the authors remove or fix that proof.","headline":"Main theorem is solid and novel, but the proof of Theorem 4.2 in Section 4 is invalid—repair or remove it.","tokens_in":16404,"tokens_out":2936,"would_cite":true,"duration_ms":26003,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05B07","05C15","05C65","05D10","05D40"],"pacs":[],"model":"deepseek-v4-flash","headline":"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$.","keywords":["Steiner triple systems","monochromatic components","edge-colorings","3-partite hole","random Steiner triple systems","Ramsey theory","hypergraphs","independence number"],"falsifier":"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.","tokens_in":15239,"feed_emoji":"🎨","tokens_out":11485,"duration_ms":97041,"temperature":0.7,"pith_summary":"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.","feed_headline":"Almost all Steiner triple systems have near-spanning components","feed_subtitle":"For any 3-coloring, a random such system has a monochromatic component on almost all the vertices.","key_machinery":"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.","core_discovery":"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$.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Introduces the cross-free/3-partite hole concept and proves the worst-case bounds that this paper extends.","marker":"[14]"},{"why":"Supplies the transfer theorems and concentration lemma that convert a high-probability property of sparse random partial Steiner triple systems into an almost-sure property of a uniformly random Steiner triple system.","marker":"[19]"},{"why":"Supplies the typical bounded differences inequality used to show that the number of cross-edges among three fixed large sets is concentrated.","marker":"[22]"},{"why":"Supplies the lemma on 3-multicolorings of complete graphs that drives the dichotomy in Theorem 2.3.","marker":"[8]"}],"fun_headline_variants":["Typical Steiner triples have near-spanning monochromatic components","Almost all Steiner triple systems yield (1-o(1))n monochromatic component","Steiner triples: largest monochromatic component tied to 3-partite hole","3-colored Steiner systems: near-spanning component for almost all","Random Steiner triple systems guarantee near-universal monochromatic component"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Typical Steiner triples have near-spanning monochromatic components","Almost all Steiner triple systems yield (1-o(1))n monochromatic component","Steiner triples: largest monochromatic component tied to 3-partite hole","3-colored Steiner systems: near-spanning component for almost all","Random Steiner triple systems guarantee near-universal monochromatic component"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000758,"raw_usage":{"total_tokens":3428,"prompt_tokens":1067,"completion_tokens":2361,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":683,"completion_tokens_details":{"reasoning_tokens":2267}},"tokens_in":683,"tokens_out":2361,"duration_ms":15712,"temperature":1.0,"reasoning_tokens":2267,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:34:46.688896+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Gy´ arf´ as","cited_arxiv_id":null,"evidence_quote":"Introduces the cross-free/3-partite hole concept and proves the worst-case bounds that this paper extends."},{"cited_title":"Almost all Steiner triple systems have perfect matchings","cited_arxiv_id":"1611.02246","evidence_quote":"Supplies the transfer theorems and concentration lemma that convert a high-probability property of sparse random partial Steiner triple systems into an almost-sure property of a uniformly random Steiner triple system."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the typical bounded differences inequality used to show that the number of cross-edges among three fixed large sets is concentrated."},{"cited_title":"DeBiasio, P","cited_arxiv_id":null,"evidence_quote":"Supplies the lemma on 3-multicolorings of complete graphs that drives the dichotomy in Theorem 2.3."}],"review_version":1}