REVIEW 2 major objections 5 minor 2 references
Proof of the Caccetta-Haggkvist conjecture for digraphs with small independence number
T0 review · 2 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read Dense digraphs with small independent sets must contain short cycles
desk verdict New special case of Caccetta–Häggkvist, but the key lemma's S_i definition is self-referential as printed and must be fixed before the proof is verifiable. 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 load-bearing object is Lemma 2.2, a structural lemma about any simple digraph with minimum out-degree $d \ge 1$, independence number $\alpha(G) \ge 3$, and girth at least $2\alpha(G)$. Fixing a vertex $v$ with out-degree exactly $d$ and setting $p = 2\alpha(G)-3$, the lemma asserts that for every odd $i \le p$ there is a unique vertex $v_i$ whose entire out-neighborhood lies inside the $i$-th in-neighborhood $N^-_i(v)$, and that the set $S_p$ of vertices not in the first out-neighborhood or the first $p$ in-neighborhoods satisfies $|V(G)\setminus S_p| \ge (2\alpha(G)-2)d+1$. The proof constructs these vertices one by one, using acyclicity of subgraphs whose independence number is reduced by stable sets, and the final counting inequality is what powers the contradictions in Theorems 2.1 and 2.2.
What would settle it
For $\alpha=3$ and $d=2$, exhaustively enumerate all simple digraphs on at most 10 vertices with minimum out-degree at least 2 and independence number 3; finding one with girth at least 6 would disprove Theorem 2.2, since the theorem guarantees a cycle of length at most $2\alpha-1=5$ whenever $n \le (2\alpha-1)d=10$.
Extended reading notes
Core claim
The central discovery is Theorem 2.3: the Caccetta–Häggkvist conjecture holds for every digraph $G$ with $\alpha(G) \le (k+1)/2$. The proof rests on two sharper statements. Theorem 2.1 shows that any simple digraph with minimum out-degree $d$ and $|V(G)| \le 2\alpha(G)d$ has girth at most $2\alpha(G)$. Theorem 2.2 improves this to girth at most $2\alpha(G)-1$ when $|V(G)| \le (2\alpha(G)-1)d$. For $\alpha(G)=2$ the result was already known; the new work assumes $\alpha(G) \ge 3$. Combining the conjecture's hypothesis $n \le kd$ with $2\alpha(G) \le k+1$ turns these bounds into a directed cycle of length at most $k$.
Load-bearing premise
The proof assumes that every edge leaving the first out-neighborhood of $v$ must go either back into that neighborhood or into the final reserved set $S_p$; if any such edge landed in an intermediate layer without creating a short cycle, the uniqueness of the $v_i$ and the counting bound would not hold, and Theorems 2.1 and 2.2 would lose their foundation.
Editorial extensions
If this is right
- If a digraph has $n \le 2\alpha(G)d$, then its girth is at most $2\alpha(G)$; this follows directly from Theorem 2.1.
- If a digraph has $n \le (2\alpha(G)-1)d$, then its girth is at most $2\alpha(G)-1$; this follows directly from Theorem 2.2.
- For any fixed independence number $\alpha$, the Caccetta–Häggkvist conjecture is true for every $k \ge 2\alpha-1$, because then $\alpha \le (k+1)/2$.
- The previously known case $\alpha(G)=2$ is recovered as a special case of the new theorem.
- Taken together, the two theorems show that the ratio $n/d$—not just the absolute size $n$—controls girth once the independence number is small.
Reading between the lines
- A natural extension would seek analogous unique vertices at even distances from $v$; if Lemma 2.2 could be pushed to all $i \le p$ rather than odd $i$, the independence-number threshold might rise from $(k+1)/2$ toward $k$.
- The counting bound $|V(G)\setminus S_p| \ge (2\alpha(G)-2)d+1$ suggests the argument's real fuel is how many vertices the absence of short cycles forces into early in-layers; optimizing this constant for general $\alpha(G)$ could yield sharper girth bounds even without new structural ideas.
- If the same machinery were applied to the bipartite or undirected analogue, it might produce a proof of a corresponding girth–independence trade-off for undirected graphs, though the directed structure of $N^-_i(v)$ appears essential.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proves the Caccetta-Häggkvist conjecture for digraphs whose independence number α(G) is at most (k+1)/2, extending a result of Lichiardopol for α(G)=2. The proof is elementary and proceeds through a structural lemma (Lemma 2.2) about the distance layers of a minimum-out-degree vertex in a digraph of large girth, followed by two theorems that convert counting information into girth bounds. Theorem 2.3 then combines these bounds with the observation that Lemma 1.1 already settles the conjecture when α(G)≤(k−1)/2. The main line of reasoning is plausible and appears correct after correcting the stated definition of the sets S_i, but the manuscript as printed contains load-bearing typos that make the central lemma unverifiable as written.
Significance. If the proof is correct after the necessary corrections, the paper establishes a genuine and nontrivial extension of the known independence-number-two case of the Caccetta-Häggkvist conjecture. The method is self-contained, uses no fitted parameters, and does not assume the conjecture. The proposed structural lemma, once its definition is repaired, is a potentially reusable tool for attacking related girth problems. However, the present text is not fully verifiable because the central lemma as printed is ill-defined; the significance is conditional on a straightforward but essential revision.
major comments (2)
- [Lemma 2.2] The printed definition of S_i is self-referential: S_i is defined as V(G) \ (N+_1(v) ∪ {v} ∪ ⋃_{i=1}^p N−_i(v)), with the same index i appearing both as the subscript of S and as the bound of the union. Literally read, all S_i are identical and independent of i, which makes the later construction of distinct vertices v_i with N+_1(v_i) ⊂ N−_i(v) impossible for odd i because the sets N−_i(v) are pairwise disjoint. The proof requires the nested definition S_i = V(G) \ (N+_1(v) ∪ {v} ∪ ⋃_{j=1}^i N−_j(v)). This is a load-bearing defect: Lemma 2.2 and consequently Theorems 2.1–2.3 are not established by the text as written.
- [Lemma 2.2 proof] In the counting step, the sentence 'N+_1(vi) ⊂ N−_1(v) gives |N−_1(v)| ≥ d' must read 'N+_1(v1) ⊂ N−_1(v)'. For i ≥ 3, the inclusion proved is N+_1(v_i) ⊂ N−_i(v), which is irrelevant to |N−_1(v)|. As printed, the displayed inequality |V(G) \ S_p| ≥ (2α(G) − 2)d + 1 is not justified; this inequality is used in both Theorem 2.1 and Theorem 2.2.
minor comments (5)
- [Lemma 2.2 statement] The text says 'an simple digraph' and the displayed complement has mismatched parentheses; both should be corrected.
- [Lemma 2.2 proof] The sentence 'Si is acyclic by Lemma 1.1' should refer to Lemma 1.2, since Lemma 1.1 is the girth bound and Lemma 1.2 is the acyclicity criterion for subgraphs of smaller independence number.
- [Lemma 2.2 proof] The assertion 'Since |N+_1(v)|=d, it follows that V(S_i) ≠ ∅' is too terse. A short justification is needed: if V(S_i)=∅, then for every w∈N+_1(v) the out-neighborhood N+_1(w) is contained in N+_1(v), but it cannot contain w, so |N+_1(w)| ≤ d−1, contradicting δ+≥d.
- [Theorem 2.1 proof] The phrase 'there is an out-neighbor wk of ud with k ≥ d' should specify that wk is chosen as the out-neighbor of ud in Sp with the largest index in the Hamiltonian path; then k ≥ d follows from |Sp|≤2d−1 and out-degree≥d, and the subsequent claim that wk has an edge outside Sp is immediate because the last vertex of a transitive tournament has no out-neighbors in Sp.
- [Theorem 2.3 proof] The proof is a single sentence; a short case distinction would make the derivation transparent: if α≤(k−1)/2, Lemma 1.1 gives g≤k; otherwise 2α = k or 2α−1 = k, and the hypothesis n≤kd makes Theorem 2.1 or Theorem 2.2 apply directly.
Circularity Check
No circularity: the proof derives the small-independence case from first principles, with Lichiardopol's alpha=2 result as the sole external input.
full rationale
The derivation chain is self-contained and non-circular. Lemma 1.1 is a direct argument from the girth and independence number of a shortest cycle, and Lemma 1.2 is an immediate corollary. Lemmas 2.1 and 2.2 are proven inside the paper using only these lemmas, the definitions of out-neighborhoods, and the assumption g(G) >= 2α(G); the key fact that every w in N+_1(v) has N+_1(w) ⊂ N+_1(v) ∪ S_p is justified by the contrapositive: if some out-neighbor of w lay outside that set, a forbidden short cycle would arise. No parameter is fitted, no target result is assumed, and no thesis is imported from the author's own prior work. The only external ingredient is Lichiardopol's theorem [2] for independence number two, cited as a separate published result; this is independent support, not a self-citation. The manuscript does contain a notational defect in Lemma 2.2: S_i is printed with ⋃_{i=1}^p N^-_i(v), which would make all S_i equal; reading it as the intended ⋃_{j=1}^i N^-_j(v) leaves the proof still a derivation rather than a circular one. That defect is a correctness/typo issue, not a circularity issue, so it does not raise the circularity score.
Assumptions & free parameters
assumptions (3)
- standard math Standard graph theory definitions and elementary set theory.
- standard math Every finite acyclic digraph has a vertex of out-degree zero.
- standard math Rédei's theorem: every tournament has a Hamiltonian path; acyclic tournaments are transitive.
Cite this review
Pith. "Pith review of Proof of the Caccetta-Haggkvist conjecture for digraphs with small independence number." pith.science (2026). https://pith.science/paper/A3WJIP2P
@misc{pith2026190802902,
author = {Pith},
title = {Pith review of: Proof of the Caccetta-Haggkvist conjecture for digraphs with small independence number},
year = {2026},
howpublished = {\url{https://pith.science/paper/A3WJIP2P}},
note = {Machine review of arXiv:1908.02902}
}
abstract
For a digraph $G$ and $v \in V(G)$, let $\delta^+(v)$ be the number of out-neighbors of $v$ in $G$. The Caccetta-H\"{a}ggkvist conjecture states that for all $k \ge 1$, if $G$ is a digraph with $n = |V(G)|$ such that $\delta^+(v) \ge n/k$ for all $v \in V(G)$, then G contains a directed cycle of length at most $k$. In [2], N. Lichiardopol proved that this conjecture is true for digraphs with independence number equal to two. In this paper, we generalize that result, proving that the conjecture is true for digraphs with independence number at most $(k+1)/2$.
Reference graph
Works this paper leans on
-
[1]
On minimal digraphs with gi ven girth
L. Caccetta, R. H¨ aggkvist, “On minimal digraphs with gi ven girth”, Congr. Numer., 21:181-187, 1978
work page 1978
-
[2]
N. Lichiardopol, “Proof of the Caccetta-H¨ aggkvist con jecture for oriented graphs with positive minimum out-degree and of independence number two”, Discrete Math, 313(14):1540-1542, 2013. 3
work page 2013
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.