REVIEW 1 major objections 3 minor 6 references
Sharp asymptotics for triangle independence and covering numbers
T0 review · 1 major / 3 minor · reviewed 2026-08-27 · deepseek-v4-flash
Pith's one-line read The sharp asymptotic constant for the sum of triangle independence and triangle cover numbers is 3/2, answering a long-standing open problem.
desk verdict Likely correct and clean solution to an open Erdős–Gallai–Tuza problem, but the upper-bound graph is misdefined in the manuscript and must be fixed before this is publishable. 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 argument is carried by a coloring lemma applied to a minimum triangle edge cover $C$ of $G$. Writing $k=\chi(C)$ and coloring $C$ properly with $k$ colors, the edges outside $C$ are partitioned into $k$ classes $R_a$ by the sum, modulo $k$, of the colors of the two endpoints. No triangle can contain two edges from the same $R_a$, because the third edge of such a triangle would lie in the covering $C$, and the two equal endpoint-color sums would force two vertices of an edge of $C$ to share a color, contradicting properness. Hence each $R_a$ is triangle-independent, so one class has at least $(m-\tau_1(G))/k$ edges and $\alpha_1(G)\ge (m-\tau_1(G))/k$. Since $C$ is $k$-chromatic, every pair of its color classes contains an edge, giving $\tau_1(G)\ge \binom{k}{2}$. Combining these two inequalities and optimizing over $k$ yields $\alpha_1(G)+\tau_1(G)\ge m/k + (k-1)^2/2$, and the arithmetic-geometric mean step produces the constant $3/2$.
What would settle it
Compute $\alpha_1$ and $\tau_1$ exactly for the constructed graph $G_m=(K_q\vee K_r)\cup sK_2$ with $q=\lfloor m^{1/3}\rfloor$, $r=\lfloor (m-\binom{q}{2})/q\rfloor$, and $s=m-\binom{q}{2}-qr$; if the exact sum is ever below $\frac{3}{2}m^{2/3}-2m^{1/3}$, or if any other $m$-edge graph is found with this property, Corollary 2.2 and Theorem 1.2 are refuted.
Extended reading notes
Core claim
The paper's central result is that $\lim_{m\to\infty} \min_{|E(G)|=m} (\alpha_1(G)+\tau_1(G))/m^{2/3} = 3/2$. More precisely, Theorem 1.2 states that every graph with $m$ edges satisfies $\alpha_1(G)+\tau_1(G) \ge \frac{3}{2}m^{2/3} - 2m^{1/3}$, and for every sufficiently large $m$ there exists an $m$-edge graph $G_m$ with $\alpha_1(G_m)+\tau_1(G_m) \le \frac{3}{2}m^{2/3} + O(m^{1/3})$. The extremal construction is the disjoint union of the split graph $K_q\vee K_r$, where a clique of size $q \approx m^{1/3}$ is completely joined to an independent set of size $r$, together with a matching of size $s$; the parameters are chosen so the total edge count is exactly $m$.
Load-bearing premise
The upper-bound construction assumes that both $\alpha_1$ and $\tau_1$ are additive over disjoint unions of graphs, so the values for the split graph and the matching component can simply be added; this standard fact is true but is not stated or proved in the paper, and the claimed upper bound depends on it.
Editorial extensions
If this is right
- Every $m$-edge graph obeys the explicit lower bound $\alpha_1(G)+\tau_1(G)\ge \frac{3}{2}m^{2/3}-2m^{1/3}$, replacing the earlier qualitative $\Omega(m^{2/3})$ bound with a concrete numerical inequality.
- The minimum in the original open problem has a limit, and the limit is $3/2$; the previously separate liminf and limsup bounds are now known to coincide.
- The bound is attained asymptotically by an explicitly described family: a clique joined to an independent set of comparable size, with a matching added, so any attempt to improve the constant must fail.
- The proof gives a structural reason for the constant: it is the value of the one-variable minimization $\min_k (m/k + (k-1)^2/2)$, so the extremal graphs are governed by the chromatic number of a minimum triangle edge cover.
Reading between the lines
- Inference: the same coloring argument could give sharp constants for variants of $\alpha_1$ and $\tau_1$ defined with respect to edge configurations other than triangles, as long as the underlying family has a similar cover-and-color structure.
- Inference: Theorem 1.2 suggests a stability statement: any graph for which $\alpha_1+\tau_1$ is within $o(m^{2/3})$ of the minimum must resemble the split-graph-plus-matching construction in its triangle-cover colour classes; such a result is not claimed in the paper.
- Inference: because the lower bound is uniform for all graphs, the explicit constant $3/2$ could serve as a benchmark for heuristics that approximate $\tau_1$ or $\alpha_1$: any computed pair of feasible solutions can be checked against this universal sum, without solving the underlying optimization exactly.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the asymptotic behaviour of α1(G)+τ1(G), where α1(G) is the maximum size of an edge set containing at most one edge from every triangle and τ1(G) is the minimum size of an edge set meeting every triangle, over graphs with m edges. The main theorem (Theorem 1.2) states that the minimum of (α1(G)+τ1(G))/m^{2/3} tends to 3/2 as m→∞, solving the Erdős–Gallai–Tuza problem. The lower bound is obtained in Proposition 2.1 via a coloring and pigeonhole argument: for a minimum triangle edge cover C, a proper coloring of C partitions the complementary edges into triangle-independent classes, yielding α1(G) ≥ (m−τ1(G))/χ(C), and the chromatic number forces τ1(G) ≥ binom(χ(C),2). Optimizing gives α1(G)+τ1(G) ≥ 3/2 m^{2/3} − 2 m^{1/3} in Corollary 2.2. The upper bound is constructed in Lemma 2.3 and the proof of Theorem 1.2: take a split graph with a clique of size q≈m^{1/3} and an independent set of size r, together with a matching of size s so that the total number of edges is exactly m; bounding the two invariants yields 3/2 m^{2/3}+O(m^{1/3}).
Significance. If the proof is formally completed, the paper resolves an open problem posed by Erdős, Gallai, and Tuza, improving the previously known bounds to a sharp constant. The lower-bound proof is a strength: it is elementary, fully self-contained, uses no free parameters, and gives an explicit additive constant. The construction for the upper bound is natural and shows the order is tight. The main concern is an internal notation inconsistency in the definition of the split graph H, which is load-bearing for the upper-bound proof but readily corrected.
major comments (1)
- [Notation and §2 (Lemma 2.3, Theorem 1.2)] The upper-bound construction uses a graph H that is inconsistently defined. In the Notation section, G∨H is defined as the join of two graphs, so K_q∨K_r is the complete graph K_{q+r}. However, before Lemma 2.3 the text says 'let H=K_q∨K_r; this split graph consists of a q-clique Q, an independent set I of size r, and all edges between Q and I.' Under the paper's own definition of ∨, I is not independent; it is a clique of size r. Consequently, the claims in the proof of Lemma 2.3 that 'I is independent' and that removing all edges inside Q leaves the complete bipartite graph between Q and I are false for the literal object. The asserted bound τ1(H)≤binom(q,2) also fails: for q=r=2, τ1(K_4)=2>1. The intended graph is evidently the join of K_q with an empty graph on r vertices (K_q∨\overline{K_r}). The definition of H must be corrected in Lemma 2.3 and in the proof of Theorem 1.2; with this correction the upper-bound proof is valid.
minor comments (3)
- [Proof of Theorem 1.2] The proof uses the additivity of α1 and τ1 over disjoint unions of graphs without stating or proving it. This is a standard fact (no triangle crosses components), but it should be mentioned for completeness.
- [Introduction, bounds from [5]] The displayed bounds '1/(3√6)' and '3√4' are ambiguous in plain text; please use unambiguous notation such as \sqrt[3]{6} and \sqrt[3]{4} if that is the intended meaning.
- [Abstract/Introduction] The phrase 'Erdős, Gallai, and Tuza proved that α1(G)+τ1(G)=Ω(m^{2/3})' uses big-Omega notation without specifying the regime; it is clear from context but could be made precise as 'for every m-edge graph' with an absolute constant.
Circularity Check
No significant circularity: the proof is self-contained and the constant 3/2 is derived, not assumed.
full rationale
The derivation is self-contained. The lower bound in Corollary 2.2 follows from Proposition 2.1, which uses only a coloring/pigeonhole argument on a minimum triangle edge cover C of G; it does not presuppose the value of alpha1(G)+tau1(G). The upper bound is an explicit construction: q=floor(m^{1/3}), r=floor((m-binom(q,2))/q), s=m-binom(q,2)-qr, and G_m is the disjoint union of the split graph H=K_q∨K_r and a matching of size s. The bounds alpha1(H)<=r+floor(q/2) and tau1(H)<=binom(q,2) are proved directly by elementary triangle-independence and triangle-cover arguments. The final estimate is arithmetic: r+s+binom(q,2)+O(1)= (3/2)m^{2/3}+O(m^{1/3}), with q determined by m rather than chosen to force the constant. No parameter is fitted to produce 3/2, and no load-bearing claim rests on a self-citation; the references to Erdős-Gallai-Tuza and other external works supply background and benchmarks, not the theorem. The paper's possible notational ambiguity about K_q∨K_r—since ∨ is defined as a join of two cliques, the literal graph is complete rather than the split graph described in Lemma 2.3—is a correctness/consistency concern, not a circularity, because even if the intended split graph is meant, the proof does not assume the target result. The unstated additivity of alpha1 and tau1 over disjoint unions is a standard true fact and is independent of the theorem being proved. Overall, the derivation chain does not reduce to its own inputs.
Assumptions & free parameters
assumptions (5)
- standard math Pigeonhole principle
- standard math Arithmetic-geometric mean inequality
- standard math Proper coloring and chromatic number of a finite graph are well-defined
- standard math If two color classes of a proper k-coloring have no edge between them, the coloring can be merged to a (k-1)-coloring
- standard math α1 and τ1 are additive over disjoint unions of graphs
Cite this review
Pith. "Pith review of Sharp asymptotics for triangle independence and covering numbers." pith.science (2026). https://pith.science/paper/V6ZRNLF6
@misc{pith2026260815561,
author = {Pith},
title = {Pith review of: Sharp asymptotics for triangle independence and covering numbers},
year = {2026},
howpublished = {\url{https://pith.science/paper/V6ZRNLF6}},
note = {Machine review of arXiv:2608.15561}
}
abstract
For a graph $G$, let $\alpha_1(G)$ be the maximum size of an edge set containing at most one edge from every triangle, and let $\tau_1(G)$ be the minimum size of an edge set meeting every triangle. Erd\H{o}s, Gallai, and Tuza proved that $\alpha_1(G)+\tau_1(G)=\Omega(m^{2/3})$ for every $m$-edge graph and asked for the optimal asymptotic constant. We prove $$\lim_{m\to\infty} \min_{G,\,|E(G)|=m} \frac{\alpha_1(G) + \tau_1(G)}{m^{2/3}} = \frac{3}{2},$$ thereby establishing that the sharp constant is $3/2$ and solving the problem.
Reference graph
Works this paper leans on
- [1]
- [2]
-
[3]
Triangle-independent sets vs. cuts
S. Norin and Y. R. Sun, Triangle-independent sets vs. cuts, arXiv preprint arXiv:1602.04370 (2016)
work page Pith review arXiv 2016
-
[4]
G. J. Puleo, On a conjecture of Erdős, Gallai, and Tuza,J. Graph Theory80(2015), no. 1, 12–17
work page 2015
-
[5]
Z. Tuza,Unsolved Combinatorial Problems, Part I, BRICS Lecture Series LS-01-1, BRICS, University of Aarhus, 2001, viii+30 pp
work page 2001
-
[6]
Xu, A note on bipartite subgraphs and triangle-independent sets,Discrete Math.340(2017), no
H. Xu, A note on bipartite subgraphs and triangle-independent sets,Discrete Math.340(2017), no. 2, 23–30. 5
work page 2017
Reviewed August 27, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.