{"id":"905a60e5-a4c6-4828-aaae-517225ce9955","arxiv_id":"1908.02902","paper_version":4,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Every digraph on n vertices with minimum out-degree at least n/k contains a directed cycle of length at most k, provided the independence number is at most (k+1)/2.","lead":"This paper proves a special case of the Caccetta-Häggkvist conjecture, a 1978 open problem about directed graphs. The result covers digraphs whose independence number is at most (k+1)/2, extending a known proof for independence number two.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 2.2's definition of S_i is self-referential as printed, making the key construction of v_i meaningless; the intended nested definition must be supplied before the proof is verifiable.","rationale":"I read the proof in good faith and checked the main combinatorial steps. The premise flagged by the reader, that every w ∈ N^+_1(v) has N^+_1(w) ⊂ N^+_1(v) ∪ S_p, is actually sound: if w had an out-neighbor outside that set, the out-neighbor would lie in {v} ∪ ⋃_{i=1}^p N^-_i(v), producing a cycle of length at most p+2 = 2α(G)−1, contradicting girth at least 2α(G). Once S_i is given the intended nested definition, the distance argument makes the 'if not' case in the choice of v_i exhaustive, and the counting of V(G) \\ S_p via the disjoint sets X_i and T_i is consistent. Theorems 2.1 and 2.2 then combine correctly with Lemma 1.1 because, if a counterexample to Conjecture 1.1 with girth at least k+1 exists under α(G) ≤ (k+1)/2, Lemma 1.1 forces k ∈ {2α(G)−1, 2α(G)}, exactly the range covered by Theorems 2.2 and 2.1 respectively. The only serious obstruction is the printed definition of S_i, which is self-contradictory: the same set cannot contain distinct vertices v_i whose out-neighborhoods lie in distinct distance layers N^-_i(v). The corrected definition is strongly suggested by the proof, so this is a corrigible but load-bearing textual error. The reader's conditional verdict already accounts for the need to correct key definitions, so I do not change the verdict.","tokens_in":4281,"tokens_out":28918,"duration_ms":296374,"concrete_test":"Rewrite Lemma 2.2 with the corrected nested definition S_i = G[V(G) \\ (N^+_1(v) ∪ {v} ∪ ⋃_{j=1}^{i} N^-_j(v))] and re-check the three uses of S_i: (a) every w ∈ N^+_1(v) has N^+_1(w) ⊂ N^+_1(v) ∪ S_p; (b) {v, v_1, ..., v_{i-2}} is stable with S_i; (c) the 'if not' case in the proof of N^+_1(v_i) ⊂ N^-_i(v) is exhaustive. If all lines hold, the concern is purely typographical and the conditional verdict stands. If any line requires a different definition, a new proof of Lemma 2.2 is needed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Lemma 2.2, S_i is printed as V(G) \\ (N^+_1(v) ∪ {v} ∪ ⋃_{i=1}^p N^-_i(v)), with the union index identical to the subscript. Taken literally, every S_i is the same set, but the proof requires S_i to be the complement of {v}, N^+_1(v), and N^-_1(v) ∪ ... ∪ N^-_i(v). The claims that V(S_i) is nonempty, that {v, v_1, ..., v_{i-2}} is stable with S_i, that α(S_i) ≤ α(G) − (i+1)/2, and that v_i can be chosen with N^+_1(v_i) ⊂ N^-_i(v) all depend on this i-dependent nested definition. With the printed definition, distinct vertices v_i for different odd i cannot exist: they would all lie in one fixed set but their out-neighborhoods would have to be contained in pairwise-disjoint layers N^-_i(v). Hence Lemma 2.2, and with it Theorems 2.1–2.3, are not established as written. The same paragraph also contains a typo in the counting step, where 'N^+_1(v_i) ⊂ N^-_1(v)' should refer to v_1 rather than v_i. Apart from this specification defect, the neighborhood facts and counting in Lemma 2.2 and the deductions in Theorems 2.1–2.2 are coherent; this is a corrigible but load-bearing textual error rather than an evident mathematical counterexample.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":4604,"tokens_out":17526,"duration_ms":163313,"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":[{"comment":"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.","section":"Lemma 2.2"},{"comment":"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.","section":"Lemma 2.2 proof"}],"minor_comments":[{"comment":"The text says 'an simple digraph' and the displayed complement has mismatched parentheses; both should be corrected.","section":"Lemma 2.2 statement"},{"comment":"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.","section":"Lemma 2.2 proof"},{"comment":"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.","section":"Lemma 2.2 proof"},{"comment":"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.","section":"Theorem 2.1 proof"},{"comment":"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.","section":"Theorem 2.3 proof"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Let me cut to the chase. Hompe proves the Caccetta–Häggkvist conjecture for digraphs with independence number at most (k+1)/2, extending Lichiardopol's 2013 theorem for α=2. That is a real new result if it holds. The proof is short and the strategy is sensible: Lemma 1.1 gives the range α≤(k−1)/2 for free, and Lemma 2.2 is the new machinery that pushes to (k+1)/2.\n\nThe good part: the nested distance-layer argument in Lemma 2.2 is a genuine structural idea, and the counting in Theorems 2.1 and 2.2 is coherent once you accept the lemma. The paper does not assume the conjecture, does not fit parameters, and cites Lichiardopol properly. No circularity.\n\nThe soft spot is not soft; it is load-bearing. As printed, Lemma 2.2 defines S_i as V(G) minus N+_1(v) ∪ {v} ∪ ⋃_{i=1}^p N^-_i(v). The union index is identical to the subscript, so every S_i is literally the same set. That makes the iterative construction of v_i meaningless. Distinct vertices v_i for different odd i would have to satisfy N+_1(v_i) ⊂ N^-_i(v), but with a single fixed S_i they would all lie in the same set, forcing one vertex to have out-neighbors in two different distance layers — impossible. The intended definition is almost certainly S_i = V(G) \\ (N+_1(v) ∪ {v} ∪ ⋃_{j=1}^i N^-_j(v)), with the inner union running to i, not to p. Once that typo is fixed, the neighborhood facts and counting line up. There is also a smaller typo in the counting paragraph where 'N+_1(v_i) ⊂ N^-_1(v)' should refer to v_1. These are corrigible, but they are not cosmetic; as written, Lemma 2.2 is not established.\n\nShould you send it to a referee? Yes. The result matters and the proof idea is credible. But the version under consideration needs a correction pass before anyone can verify it. I would accept it for peer review and ask for a revision that fixes the definition and the typo, rather than desk-rejecting. The math looks honest and the extension is meaningful.","headline":"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.","tokens_in":5076,"tokens_out":6901,"would_cite":false,"duration_ms":62896,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C20","05C38","05C69","05C35"],"pacs":[],"model":"deepseek-v4-flash","headline":"Dense digraphs with small independent sets must contain short cycles","keywords":["Caccetta-Häggkvist conjecture","directed cycles","girth","independence number","minimum out-degree","digraphs","extremal graph theory"],"falsifier":"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$.","tokens_in":4090,"feed_emoji":"🔄","tokens_out":11344,"duration_ms":103396,"temperature":0.7,"pith_summary":"The paper proves the Caccetta–Häggkvist conjecture in a new range: if $G$ is a digraph on $n$ vertices with minimum out-degree at least $n/k$ and independence number $\\alpha(G) \\le (k+1)/2$, then $G$ contains a directed cycle of length at most $k$. This extends the previously known case $\\alpha(G)=2$ to all independence numbers up to about half the target cycle length. The proof shows that a digraph with no such short cycle is forced to have a large independent set, contradicting the assumed bound. The result matters because the conjecture is a central open problem in extremal digraph theory, and this proof identifies a clean trade-off between girth and independence number.","feed_headline":"Dense digraphs with small independent sets must contain short cycles","feed_subtitle":"The Caccetta-Häggkvist conjecture is confirmed whenever α(G) ≤ (k+1)/2.","key_machinery":"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.","core_discovery":"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$.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Formulates the Caccetta–Häggkvist conjecture, the statement the paper sets out to prove in a restricted range.","marker":"[1]"},{"why":"Supplies the base case $\\alpha(G)=2$, which the paper invokes to assume $\\alpha(G) \\ge 3$ in the main lemmas.","marker":"[2]"}],"fun_headline_variants":["Caccetta-Häggkvist proven for α(G)≤(k+1)/2","Small independent sets force short directed cycles","CH conjecture true when α(G)≤(k+1)/2","New girth bound proves CH for small α","Girth bound yields CH proof for α≤(k+1)/2"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Caccetta-Häggkvist proven for α(G)≤(k+1)/2","Small independent sets force short directed cycles","CH conjecture true when α(G)≤(k+1)/2","New girth bound proves CH for small α","Girth bound yields CH proof for α≤(k+1)/2"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001724,"raw_usage":{"total_tokens":6788,"prompt_tokens":883,"completion_tokens":5905,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":499,"completion_tokens_details":{"reasoning_tokens":5814}},"tokens_in":499,"tokens_out":5905,"duration_ms":48464,"temperature":1.0,"reasoning_tokens":5814,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:32:32.940266+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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$.","supporting_citations":[{"cited_title":"On minimal digraphs with gi ven girth","cited_arxiv_id":null,"evidence_quote":"Formulates the Caccetta–Häggkvist conjecture, the statement the paper sets out to prove in a restricted range."},{"cited_title":"Proof of the Caccetta-H¨ aggkvist con jecture for oriented graphs with positive minimum out-degree and of independence number two","cited_arxiv_id":null,"evidence_quote":"Supplies the base case $\\alpha(G)=2$, which the paper invokes to assume $\\alpha(G) \\ge 3$ in the main lemmas."}],"review_version":1}