{"id":"fac4422a-3e97-42f4-b522-702f959ca913","arxiv_id":"2411.19267","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For twin-free K_r-saturated graphs, the minimum edge count is asymptotically between (r+2)n and (r+3)n, and for triangles between (5+2/3)n and 6n.","lead":"This paper introduces a twin-free version of the classic graph saturation problem, where no two vertices may share the same neighbors. It proves that such graphs always exist for large n and gives the first bounds on how few edges they can have, roughly between 5.67n and 6n for triangles.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lower bounds in Theorems 2 and 3 hinge on the unproved companion theorem [1, Thm 4] that O(n)-edge K_r-saturated graphs have O(n/log n) vertex covers; if false or misstated, the main asymptotic lower bounds reduce to (r+1)n.","rationale":"The reader's weakest_assumption is exactly the companion theorem, and my reading of Section 4 confirms that every lower bound in Theorems 2 and 3 funnels through this one external result. The internal r-system framework is coherent: Observation 1 cleanly characterizes K_r-saturation via maximal r-systems, the estimates in Theorem 4 are used consistently, and the double-counting argument in Theorem 6(5) for the 2s/3 lower bound checks out. I found no internal contradiction or invalid step that would independently threaten the main results. However, the dependence on [1, Theorem 4] is not cosmetic: the o(n) term in the lower bounds comes entirely from m=O(n/log n). Without it, the counting of low-degree vertices outside C gives only an O(n) error, which is the same order as the gap between (r+1)n and the claimed (r+2)n. I therefore agree with the reader's CONDITIONAL verdict and recommend no change, pending independent verification of the companion theorem.","tokens_in":50,"tokens_out":7818,"duration_ms":131709,"concrete_test":"Independently verify [1, Theorem 4] by reading arXiv:2302.13389 and re-deriving the O(n/log n) vertex-cover bound for an arbitrary K_r-saturated graph with e(G)=O(n). In particular, check the exact hypotheses: (i) does the proof require the graph to be twin-free, or to have minimum degree exactly r-2, or to satisfy any other condition beyond saturation and e(G)=O(n)? (ii) does the Two Families Theorem argument produce a vertex cover from the endpoints of a maximal matching? Then re-run the lower-bound paragraph in Section 4 with the actual bound from [1] in place of m=O(n/log n); if the correct bound is only O(n), the lower bounds in Theorems 2(1), 2(2), 3(3), and 3(4) collapse.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The lower-bound halves of all four parts of Theorem 2 and Theorem 3 are obtained in Section 4 by first invoking Theorem 4 of [1]: every K_r-saturated graph with e(G)=O(n) has a vertex cover C of size m=O(n/log n). This theorem is not stated or proved here and is not a standard textbook result. The subsequent counting of vertices outside C of degree at most r+1 uses the estimates s_{r,t}(m) << m from Theorem 4 of this paper; these bounds give only |F_t|=O(m). The claimed lower bounds (r+2)n and (5+2/3)n require m=o(n), i.e. m=O(n/log n), not merely m=O(n). If [1, Theorem 4] is false, has hidden hypotheses (e.g. only for graphs with minimum degree exactly r-2, only for twin-free graphs, or only for the extremal graph), then |F_t| could be Theta(n), the term e(C,V(G)\\C) gains an O(n) error, and the stated lower bounds would reduce to (r+1)n. No proof or even precise statement of [1, Theorem 4] is included here, so the central lower bounds are conditional on an external, unverified result.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies twin-free K_r-saturated graphs. It introduces tsat(n,K_r) and the minimum-degree variant tsat(n,K_r,t), proves a complete existence characterization in Theorem 1, and gives two-sided linear bounds in Theorems 2 and 3. The central quantitative claims are (5+2/3)n+o(n) ≤ tsat(n,K3) ≤ 6n+o(n), (r+2)n+o(n) ≤ tsat(n,K_r) ≤ (r+3)n+o(n) for r ≥ 4, and analogous bounds with sublinear corrections for tsat(n,K_r,t) when t ≥ r+3. The proofs are organized around r-systems and auxiliary extremal quantities s_{r,t}(m), e_{r,t}(s), and e'_{r,t}(s), with estimates developed in Theorems 4 through 8.","tokens_in":34895,"tokens_out":32253,"duration_ms":294847,"significance":"If the main theorems are correct, this is a meaningful contribution to saturation theory: it isolates the effect of twin-freeness on the classical Erdős–Hajnal–Moon extremal construction, gives an exact existence characterization, and establishes two-sided bounds with explicit constants. The r-system framework and the associated extremal problems for maximally independent sets of fixed size in triangle-free graphs are natural and likely to be reused. The paper contains explicit constructions and a long chain of estimates, and I did not find evidence of parameter fitting or circular reasoning: the auxiliary quantities are defined independently of the claimed bounds. The main reservation is that the lower-bound proofs depend on structural results from the companion paper [1] that are neither stated nor proved in the present manuscript, which makes the central claims conditional as written.","major_comments":[{"comment":"The lower-bound halves of Theorem 2 (and the analogous lower bounds in Theorem 3) invoke [1, Theorem 4] to obtain a vertex cover C of size m = O(n/log n). This theorem is load-bearing: the subsequent estimates |F_t| ≤ s_{r,t}(m) = O(m) only imply that the number of vertices outside C of degree at most r+1 is O(m), and the claimed coefficient r+2 (or 17/3 for r=3) requires m = o(n). If [1, Theorem 4] is false, has hidden hypotheses, or applies only to a restricted class of K_r-saturated graphs, the lower bound reduces to (r+1)n. Since the theorem is not stated or proved in this paper and is not a standard textbook result, the revision should state it precisely, verify that the present hypotheses match it, and either prove it or give a self-contained substitute.","section":"Section 4, proof of Theorem 2 lower bounds"},{"comment":"The proof of Theorem 8 begins with 'By Lemma 4 in [1]' and then uses the set S and the alternative inequalities involving |Γ(v)∩S| and |Γ(v)\\S|. Parts 1 and 2 of Theorem 3 are derived from Theorem 8, so this is a second external load-bearing lemma. The manuscript does not state Lemma 4 or its hypotheses, so the proof of Theorem 8 cannot be checked from the text as it stands. The revision should include the statement and proof, or at minimum show explicitly that the hypotheses of the present paper (δ(G) ≥ t and the twin-pair condition) satisfy the lemma.","section":"Section 4, proof of Theorem 8"},{"comment":"With H = G[C ∪ S], the displayed identity e(G) = e(H) + e(C, V(G)\\C) is not correct: it counts the edges between C and S twice. The correct decomposition is e(G) = e(H) + e(C, V(G)\\(C∪S)), equivalently e(G) = e(C) + e(C, V(G)\\C). Because |S| ≤ t|C| = O(n/log n), the resulting asymptotic lower bound is unchanged up to an O(n/log n) error, but the displayed equality should be repaired or replaced by an inequality with this error term.","section":"Section 4, proof of Theorem 3 lower bounds"}],"minor_comments":[{"comment":"The sentence 'Adding r−3 conical vertices then gives a twin-free Kr-saturated graph on r+k vertices' should read 'on k+r−3 vertices'; as written the vertex count is inconsistent with the preceding construction.","section":"Proof of Theorem 1"},{"comment":"The estimate e(G) ≥ (r+2)n + O(n/log n) should be written as e(G) ≥ (r+2)n − O(n/log n); with plus O the displayed inequality is misleading because the O(n/log n) vertices outside C of degree at most r+1 subtract from the ideal count.","section":"Section 4, proof of Theorem 2 lower bounds"},{"comment":"The notation e'_{r,t}[n+o(n)] uses a real-valued argument; please clarify that it means for every integer N = n+o(n) (or for the least such integer) and that the estimates are uniform.","section":"Statements of Theorems 3, 6, and 8"},{"comment":"Property 5 in Construction 1, including the maximality of (H'_{t,l},F'_{t,l}) and the O(l^3) bound on missing edges for t=4, is asserted as 'easy to check' and is used in the upper bounds of Theorems 2 and 6; a proof or a detailed verification would strengthen the paper.","section":"Construction 1"},{"comment":"There are several small typos: 'turn out be' in the abstract, 'is is roughly' in Section 3, and 'Theoerem' in Remark 3.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The main gap is a heavy dependence on the companion paper [1], specifically [1, Theorem 4] and [1, Lemma 4]. If [1] is already accepted with full proofs, the dependence is less serious but should still be documented explicitly in the paper. The editor may also wish to ask for the 'easy to check' verifications of the explicit graphs in Theorem 1 and Construction 1, since several of those assertions are load-bearing for the existence and upper-bound arguments. I found no evidence of circularity or parameter fitting."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper defines tsat(n,K_r), the minimum number of edges in a twin-free K_r-saturated graph, and gives the first bounds: (r+2)n ≤ tsat(n,K_r) ≤ (r+3)n, with a stronger lower bound (5+2/3)n for r=3. That is a genuinely new parameter and a clean pair of theorems. The existence classification in Theorem 1 is complete and also new. The r-systems framework is a reasonable abstraction, and the auxiliary results — s_{r,t}(m), e_{r,t}(s), the exact s'_{3,3}(m)=m+O(1), and the constant 2/3 lower bound on e_{3,5}(s) — are substantial. The connection to maximizing and minimizing maximally independent sets in K3-free graphs is a useful byproduct and likely to be cited independently.\n\nThe main soft spot is the lower-bound machinery. Both Theorem 2 and Theorem 3 lower bounds assume Theorem 4 of the companion paper [1]: every K_r-saturated graph with O(n) edges has a vertex cover of size O(n/log n). That theorem is not stated or proved here, and it is doing real work: without the o(n) size, the counting of small-degree vertices outside the cover gives only (r+1)n. The companion paper is listed as to appear in the Electronic Journal of Combinatorics, so this may be a legitimate dependency, but a referee cannot check the heart of the paper without that external result. The paper would be stronger if it stated the theorem precisely or proved a sufficiently strong special case. I would want the referee to verify [1] carefully.\n\nThere are also a lot of 'it is easy to check' steps, especially in Theorem 1's small-case classification and the constructions. Most are probably fine, but in a proof where the main structural facts come from an external paper, this style adds friction. Section 4 is long; the proof of Theorem 9 is intricate and self-contained — credit where it is due.\n\nAll that said, the central argument is not circular; the auxiliary quantities are defined independently, and the bounds are not fitted. If [1, Thm 4] holds, the paper's main results follow as stated. I do not see a load-bearing flaw in the internal reasoning on a first read, just an external dependency that needs checking.\n\nThe paper is for people working on saturation numbers, and possibly on maximal independent set counts in sparse graphs. It deserves a serious referee, but the reviewer should read [1] first, or at minimum demand a precise statement of its Theorem 4. My recommendation: send it to peer review, with a referee brief that flags the companion theorem. I would cite it in my own work on saturation.","headline":"New twin-free saturation parameter with first bounds; the main lower bounds rely on an unproved companion theorem that a referee will need to check.","tokens_in":35437,"tokens_out":2990,"would_cite":true,"duration_ms":27269,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C35","05C69","05D05"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that twin-free $K_r$-saturated graphs require asymptotically between $(r+2)n$ and $(r+3)n$ edges, and that the triangle case is bounded below by $5 + \\frac{2}{3}$ times $n$ and above by $6n$.","keywords":["twin-free saturation","K_r-saturated graphs","K_3-free graphs","maximal independent sets","extremal graph theory","r-systems","minimum degree","intersecting families"],"falsifier":"Find, for arbitrarily large $n$, a twin-free $K_3$-saturated graph on $n$ vertices with fewer than $(5+\\frac{2}{3})n$ edges; equivalently, with average degree below $11\\frac{1}{3}$. Such a graph would disprove the triangle lower bound of Theorem 2 outright. A less direct test would be to exhibit a $K_r$-saturated graph with $O(n)$ edges whose smallest vertex cover has size $\\Omega(n)$, which would refute the companion lemma on which the proof relies.","tokens_in":34409,"feed_emoji":"🔺","tokens_out":11130,"duration_ms":90423,"temperature":0.7,"pith_summary":"The classical saturation problem asks for the fewest edges in a graph that is just short of containing a clique $K_r$; the 1964 solution has many pairs of twin vertices. This paper asks what happens when twins are banned, defining $tsat(n,K_r)$ as the minimum edge count of a twin-free $K_r$-saturated graph. The main result is that $tsat(n,K_3)$ lies between $(5+\\frac{2}{3})n+o(n)$ and $6n+o(n)$, while for every $r\\geq 3$ the bounds $(r+2)n+o(n) \\leq tsat(n,K_r) \\leq (r+3)n+o(n)$ hold. A companion theorem shows twin-free $K_r$-saturated graphs exist for all sufficiently large $n$, with only four small exceptions. The proof reduces a sparse twin-free saturated graph to a tiny vertex cover plus an intersecting family of maximally independent sets in a $K_3$-free graph, which is why the triangle case carries the sharper constant.","feed_headline":"Twin-free triangles cost at least 5.67n edges","feed_subtitle":"Classic clique-saturated graphs rely on twins; removing them pushes triangle saturation from about n to between 5.67n and 6n.","key_machinery":"The central object is an $r$-system $(H,\\mathcal{F})$: $H$ is $K_r$-free, every $S\\in\\mathcal{F}$ is a maximally $K_{r-1}$-free set in $H$, and any two distinct sets in $\\mathcal{F}$ intersect in a set containing $K_{r-2}$. The observation that $G(H,\\mathcal{F})$ is $K_r$-saturated exactly when $(H,\\mathcal{F})$ is a maximal $r$-system converts saturation into extremal questions about such systems, with $s_{r,t}(m)$ bounding the size of $\\mathcal{F}$ and $e_{r,t}(s)$ bounding the edges of $H$. For triangles the paper works with the variant $(3,t)'$-system that drops the intersection condition, and the two load-bearing quantitative facts are $s'_{3,3}(m)=m+O(1)$ and $e_{3,5}(s)\\geq \\frac{2}{3}s+o(s)$; these produce the $5+\\frac{2}{3}$ triangle constant.","core_discovery":"The central claim is that forbidding twins in $K_r$-saturated graphs raises the asymptotic edge count from the classical $(r-2)n$ to at least $(r+2)n$ and at most $(r+3)n$, with the triangle case satisfying the stronger pair of bounds $(5+\\frac{2}{3})n+o(n)$ and $6n+o(n)$. The same linear bounds hold for the minimum-degree refinement $tsat(n,K_r,t)$ whenever $t\\leq r+2$ (for triangles, $t\\leq 5$), while for larger $t$ the excess over $tn$ is a sublinear power of $n$: the range is $\\Omega(n^{1/(t-r+2)})$ to $O(n^{4/(t-r+2)})$, with improved triangle exponents. The lower-bound method passes through a vertex cover of size $O(n/\\log n)$: outside the cover, every vertex is represented by its neighbourhood, and the saturated condition turns these neighbourhoods into a family of maximally $K_{r-1}$-free sets with pairwise intersections containing a $K_{r-2}$, a structure the paper calls an $r$-system. Estimating the extremal functions of these systems yields the linear constants; explicit constructions of $K_3$-free graphs with many size-$t$ maximally independent sets supply the matching upper bounds.","pith_inferences":["Editorial extension: the small-vertex-cover reduction may be a general route to proving $tsat(n,H)=\\Omega(n)$ for other forbidden graphs $H$ whose extremal saturators are blow-ups, turning twin-free saturation into an intersecting-family problem for general $H$.","Editorial extension: the gap between $5\\frac{2}{3}n$ and $6n$ for triangles is concrete; a computational search on twin-free $K_3$-saturated graphs with, say, $n$ up to a few hundred could indicate whether the true constant sits closer to the lower obstruction or to the $6n$ construction.","Editorial extension: if the companion vertex-cover lemma could be upgraded from $O(n/\\log n)$ to $o(n)$ with explicit constants, the method would yield a fully self-contained proof of the linear lower bounds without relying on an external paper's structural theorem."],"forward_implications":["If the lower bounds are right, the twin-free condition changes the asymptotic constant for clique saturation from $(r-2)n$ to somewhere between $(r+2)n$ and $(r+3)n$, more than doubling it for triangles.","The triangle constant is tied to size-five maximally independent sets in $K_3$-free graphs: any improvement on $e_{3,5}(s)\\geq \\frac{2}{3}s+o(s)$ would directly improve the $5+\\frac{2}{3}$ lower bound.","For the minimum-degree variant $tsat(n,K_r,t)$, the same linear asymptotics hold for all small $t$, so a low minimum-degree requirement does not force extra edges beyond the twin-free baseline; for larger $t$ the excess over $tn$ grows as a sublinear power of $n$.","Twin-free $K_r$-saturated graphs exist for every $n$ except $n=r$, $n=r+1$, and the two small triangle cases $n=6,7$, so the problem is well-posed for all large orders."],"supporting_citations":[{"why":"The companion paper supplies the $O(n/\\log n)$ vertex-cover theorem for every $K_r$-saturated graph with $O(n)$ edges; every lower bound in Theorems 2 and 3 invokes this structural lemma.","marker":"[1]"},{"why":"The classical 1964 determination of $sat(n,K_r)=(r-2)n+o(n)$ provides the baseline value and the extremal graph with many twins that motivates the twin-free problem and fixes the minimum possible degree $r-2$.","marker":"[4]"},{"why":"The intersection theorem for families of finite sets bounds the size of an $r$-system's family by ${m-r+2 \\choose t-r+2}$, which is used to prove the upper bound on $s_{r,t}(m)$ that feeds the large-$t$ estimates in Theorem 3.","marker":"[5]"}],"fun_headline_variants":["Twin-free triangles need at least 5.67n edges","Twin-free K_r saturation: (r+2)n to (r+3)n edges","Removing twins pushes K_r saturation cost to (r+2)n","Twin-free saturation: edge count jumps to (r+2)n or more","Twin-free graphs tie saturation to maximal independent sets"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The lower-bound proofs depend on a structural lemma proved in the companion paper, not here: every $K_r$-saturated graph with linearly many edges has a vertex cover of size $O(n/\\log n)$, and if that lemma fails the counting argument behind the $(r+2)n$ and $(5+\\frac{2}{3})n$ lower bounds collapses.","fun_headline_variants_meta":{"raw":{"variants":["Twin-free triangles need at least 5.67n edges","Twin-free K_r saturation: (r+2)n to (r+3)n edges","Removing twins pushes K_r saturation cost to (r+2)n","Twin-free saturation: edge count jumps to (r+2)n or more","Twin-free graphs tie saturation to maximal independent sets"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001492,"raw_usage":{"total_tokens":6100,"prompt_tokens":1169,"completion_tokens":4931,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":785,"completion_tokens_details":{"reasoning_tokens":4833}},"tokens_in":785,"tokens_out":4931,"duration_ms":32908,"temperature":1.0,"reasoning_tokens":4833,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T10:21:31.843852+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Find, for arbitrarily large $n$, a twin-free $K_3$-saturated graph on $n$ vertices with fewer than $(5+\\frac{2}{3})n$ edges; equivalently, with average degree below $11\\frac{1}{3}$. Such a graph would disprove the triangle lower bound of Theorem 2 outright. A less direct test would be to exhibit a $K_r$-saturated graph with $O(n)$ edges whose smallest vertex cover has size $\\Omega(n)$, which would refute the companion lemma on which the proof relies.","supporting_citations":[{"cited_title":"$K_r$-saturated Graphs and the Two Families Theorem","cited_arxiv_id":"2302.13389","evidence_quote":"The companion paper supplies the $O(n/\\log n)$ vertex-cover theorem for every $K_r$-saturated graph with $O(n)$ edges; every lower bound in Theorems 2 and 3 invokes this structural lemma."}],"review_version":1}