REVIEW 3 major objections 4 minor 21 references
Proof of the KAMAK tree conjecture
T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read The paper proves that every grounded tree appears as a subdigraph in every digraph of sufficiently large minimum out-degree, confirming the KAMAK tree conjecture and completing the characterization of unavoidable digraphs as grounded…
desk verdict The broom-digraph machinery is promising and the sufficiency direction is genuinely new, but the central induction rests on two false numerical inequalities, so the conjecture remains unproved by this manuscript. 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 $(k,d)$-broom digraphs: digraphs built as a union of $(k,d)$-brooms, each a balanced out-arborescence of height at most $k$ rooted at a vertex of a root set $R$, with all leaves in $R$, internal vertices outside $R$, and distinct brooms intersecting only in $R$. Within such digraphs the proof uses $t$-typed structure, meaning each vertex carries a binary type that predicts, for each distance $i$ up to $t$, whether every directed walk of length $i$ from it ends in the root set. These type constraints let the embedding control exactly where paths hit the root set while attaching a removed leaf, and high in-degree at root vertices provides the room to place that leaf. The decisive lemma embeds any max-grounded tree into a sufficiently large broom digraph by peeling off a leaf of minimum height and using the typed structure to extend the smaller embedding.
What would settle it
For $k=10$ and a grounded tree $T$ with $|V(T)|=10$, set $d=10^{13} k^3 (8k)^k$ and check whether $d^{1/(8k)} \geq 10^{13} k^3 (8k)^{k-1}$. Direct substitution gives a left-hand side of about 3 and a right-hand side of about $10^{33}$, so the inequality is false; this calculation shows that the degree descent in Lemma 3.2 does not hold for the stated constants.
Extended reading notes
Core claim
Theorem 1.3 states that every grounded tree is $\delta^+$-enforcible. A grounded tree is an oriented tree whose vertices of in-degree at least two all sit at the same height in the tree's unique height function; the KAMAK conjecture predicted exactly these trees are unavoidable. The proof reduces the statement to max-grounded trees, where the high-in-degree vertices occupy the maximum height, and then proves a stronger embedding lemma: every max-grounded tree on $k$ vertices appears as a proper copy in every $(k,d)$-broom digraph with $d \geq 10^{13} k^3 (8k)^k$. Because every digraph of minimum out-degree $d$ can be regarded as a $(k,d)$-broom digraph, the lemma yields the theorem and, with the known necessity direction, the characterization that $\delta^+$-enforcible digraphs are precisely the grounded forests.
Load-bearing premise
The proof's induction in Lemma 3.2 relies on the numerical inequality that the new broom degree $d' = \lceil d^{1/(8k)} \rceil$ obtained from Lemma 2.11 is still at least $10^{13} k^3 (8k)^{|V(T)|-1}$; if this inequality fails, the step from $|V(T)|$ to $|V(T)|-1$ cannot be carried out.
Editorial extensions
If this is right
- Corollary 1.4 completes the classification: a digraph is $\delta^+$-enforcible if and only if it is a grounded forest.
- The quantitative bound from the proof shows the threshold $d_k$ for grounded trees on $k$ vertices exists and is at most about $2^{O(k)}$.
- The forest case follows by embedding each component separately, so the theorem covers all grounded forests, not just trees.
- The stronger embedding lemma applies to every $(k,d)$-broom digraph with $d$ large enough, giving a reusable structural template for embeddings into high-out-degree digraphs.
Reading between the lines
- The broom-digraph decomposition isolates the path structure of high-out-degree digraphs, so a similar typed-embedding strategy could be tried for other unavoidability problems, such as subdivisions of acyclic digraphs beyond the grounded case.
- The use of the Lovász local lemma and Chernoff bounds suggests the constants are far from optimal; derandomizing the pruning steps might lower the shown threshold.
- A natural extension is to ask whether the grounded-forest characterization persists under other degree notions, for instance minimum semi-degree or minimum in-degree together with a bound on out-degree.
- The numerical inequality connecting the degree descent with the size of the tree is the tightest step in the proof; a different descent that preserves more of the base $(8k)^{|V(T)|}$ would make the argument hold under milder assumptions on the constants.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper claims a proof of the KAMAK tree conjecture: every grounded tree is delta-plus-enforcible (Theorem 1.3), which would imply a characterization of delta-plus-enforcible digraphs as grounded forests (Corollary 1.4). The proof introduces (k,d)-broom digraphs, proves structural lemmas for finding sub-brooms with high in-degree roots (Lemma 2.6) and typed brooms (Lemma 2.10), combines them (Lemma 2.11), and then uses a minimal-counterexample induction (Lemma 3.2) to embed any max-grounded tree into any (k,d)-broom with sufficiently large d. The text is self-contained and follows the strategy outlined by Hons et al.
Significance. If correct, this would resolve an open conjecture and give a complete characterization of delta-plus-enforcible digraphs. The paper is clearly written and uses standard tools (Lovasz local lemma, Ramsey-type pruning). The reduction to max-grounded trees and the broom-digraph framework are natural and potentially useful. However, the proof as written contains two false numerical inequalities in the central induction, so the main theorem is not established.
major comments (3)
- [Lemma 2.11] In the proof of Lemma 2.11, the inequality floor(d^(1/(7k))) / 2^(k(k-1)/2) >= d^(1/(8k)) is asserted without proof and is false in the relevant parameter range. For example, with k=10 and d=10^13*k^3=10^16, the left-hand side is at most 1/2^45, which is about 2.8e-14, while the right-hand side is 10^(1/5) ~ 1.58. Thus the existence of the claimed k-typed (k, ceil(d^(1/(8k))))-broom subdigraph does not follow from Lemma 2.10 applied to H. This invalidates Lemma 2.11 as used in the proof of Lemma 3.2.
- [Lemma 3.2] After applying Lemma 2.11, the proof asserts that d' = ceil(d^(1/(8k))) >= 10^13*k^3*(8k)^|V(T')|, where T' = T - l. This inequality is false. From d >= 10^13*k^3*(8k)^|V(T)| one obtains d^(1/(8k)) at most roughly (10^13*k^3)^(1/(8k))*(8k)^(1/8), whereas the claimed lower bound is 10^13*k^3*(8k)^(|V(T)|-1). For |V(T)| >= 2 and k >= 2, the right-hand side grows like (8k)^(|V(T)|-1), while the left-hand side grows only like (8k)^(1/8); the inequality already fails at k=10, |V(T)|=2. Consequently, the minimal counterexample T cannot be shown to satisfy the lemma's hypothesis for T', and the induction step cannot be carried out. This is the central load-bearing step of the proof.
- [Theorem 1.3] Because Lemma 3.2 is not established, the deduction of Theorem 1.3 from Observation 3.1 and Lemma 3.2 fails as written. In particular, the bound d(T) = 10^13*k^3*(8k)^k stated in the proof of Theorem 1.3 is unsupported, and a different quantitative parameter choice would be needed even if the general strategy could be repaired.
minor comments (4)
- [Introduction] There are minor typos: 'terminlogy' should be 'terminology' and 'vice-versa' should be 'vice versa'.
- [Lemma 3.2] The statement 'as well as delta^-(D') >= 1' after applying Lemma 2.11 is not a consequence of Lemma 2.11 and is not used later; please remove or justify it.
- [Lemma 3.2] The final sentence, 'As we found the desired contradiction in each of the three cases, this means that our initial assumption on the existence of T was correct', is confusing; it should say that the assumption that the lemma fails leads to a contradiction.
- [Lemma 3.2, Case 2] The claim that each root vertex has at most one in-neighbor in each constituent (k,d)-broom is true but not immediate from Definition 2.2 alone; a brief explanation would improve readability.
Circularity Check
No significant circularity: the main proof is self-contained and does not reduce its conclusion to its assumptions.
full rationale
The paper proves the KAMAK tree conjecture (Theorem 1.3) by a self-contained construction. The necessity direction and the conjecture statement are cited from Hons et al., but the sufficiency proof does not use the conjecture as an input; it develops broom digraphs, proves the auxiliary Lemmas 2.5, 2.6, 2.8, 2.10, and 2.11 from first principles, and then embeds any grounded tree via the minimal-counterexample induction in Lemma 3.2. No parameter is fitted to the target result, and no prediction is extracted from data. The only self-citations are contextual references to the authors' earlier work on digraph splitting and oriented cycles, which are not load-bearing for the main theorem. The numerical inequality concerns raised by a reviewer are correctness risks, not instances of circular reasoning: a false inequality would invalidate the induction, but it would not make the argument circular.
Assumptions & free parameters
assumptions (4)
- standard math Lovász local lemma (Lemma 2.4) is used to find a random sparsification with controlled out- and in-degrees.
- standard math Chernoff bounds are used to estimate the probability of bad events in the same sparsification.
- standard math Pigeonhole principle is used in Lemma 2.8 to pass to monochromatic leaves.
- domain assumption A digraph with minimum out-degree d can be assumed to have out-degree exactly d at every vertex by deleting arcs.
Cite this review
Pith. "Pith review of Proof of the KAMAK tree conjecture." pith.science (2026). https://pith.science/paper/QVX7BGRF
@misc{pith2026250521367,
author = {Pith},
title = {Pith review of: Proof of the KAMAK tree conjecture},
year = {2026},
howpublished = {\url{https://pith.science/paper/QVX7BGRF}},
note = {Machine review of arXiv:2505.21367}
}
read the original abstract
There are many intriguing questions in extremal graph theory that are well-understood in the undirected setting and yet remain elusive for digraphs. A natural instance of such a problem was recently studied by Hons, Klimo\v{s}ov\'{a}, Kucheriya, Mik\v{s}an\'{i}k, Tkadlec and Tyomkyn: What are the digraphs that have to appear as a subgraph in all digraphs of sufficiently large minimum out-degree? Hons et al. showed that all such digraphs must be oriented forests with a specific structure, and conjectured that vice-versa all oriented forests with this specific structure appear in any digraph of sufficiently large minimum out-degree. In this paper, we confirm their conjecture.
Figures
Reference graph
Works this paper leans on
-
[1]
P. Aboulker, N. Cohen, F. Havet, W. Lochet, P. F. S. Moura, and S. Thomass´ e. Subdivisions in digraphs of large out-degree or large dichromatic number. Electron. J. Combin., 26(3):Paper No. 3.19, 18, 2019
work page 2019
-
[2]
N. Alon. Disjoint directed cycles. J. Combin. Theory Ser. B, 68(2):167–178, 1996
work page 1996
-
[3]
N. Alon. Splitting digraphs. Combin. Probab. Comput., 15(6):933–937, 2006
work page 2006
-
[4]
J.-C. Bermond and C. Thomassen. Cycles in digraphs – a survey. J. Graph Theory, 5(1):1–43, 1981
work page 1981
-
[5]
B. Bollob´ as and A. Thomason. Proof of a conjecture of Mader, Erd˝ os and Hajnal on topological complete subgraphs. European J. Combin., 19(8):883–887, 1998
work page 1998
-
[6]
M. Buci´ c. An improved bound for disjoint directed cycles. Discrete Math., 341(8):2231–2236, 2018
work page 2018
-
[7]
L. Caccetta and R. H¨ aggkvist. On minimal digraphs with given girth. In Proceedings of the Ninth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1978), volume XXI of Congress. Numer., pages 181–187. Utilitas Math., Winnipeg, MB, 1978
work page 1978
-
[8]
M. Christoph, K. Petrova, and R. Steiner. A note on digraph splitting. Combin. Probab. Comput., 2025
work page 2025
Show all 21 references
-
[9]
Gishboliner, R
L. Gishboliner, R. Steiner, and T. Szab´ o. Oriented cycles in digraphs of large outdegree. Combinatorica, 42:1145–1187, 2022
2022
-
[10]
Hladk´ y, D
J. Hladk´ y, D. Kr´ al’, and S. Norin. Counting flags in triangle-free digraphs. Combinatorica, 37(1):49–76, 2017
2017
-
[11]
T. Hons, T. Klimoˇ sov´ a, G. Kucheriya, D. Mikˇ san ´ ık, J. Tkadlec, and M. Tyomkyn. Unavoidable subgraphs in digraphs with large out-degrees, 2025. 11
2025
-
[12]
Koml´ os and E
J. Koml´ os and E. Szemer´ edi. Topological cliques in graphs.Combin. Probab. Comput., 3(2):247– 256, 1994
1994
-
[13]
Koml´ os and E
J. Koml´ os and E. Szemer´ edi. Topological cliques in graphs. II. Combin. Probab. Comput., 5(1):79–90, 1996
1996
-
[14]
W. Mader. Degree and local connectivity in digraphs. Combinatorica, 5(2):161–165, 1985
1985
-
[15]
W. Mader. On topological tournaments of order 4 in digraphs of outdegree 3. J. Graph Theory, 21(4):371–376, 1996
1996
-
[16]
Stiebitz
M. Stiebitz. Decomposition of graphs and digraphs. In KAM Series in Discrete Mathematics- Combinatorics-Operations Research-Optimization, volume 309, pages 56–59. Charles Univer- sity, Prague, 1995
1995
-
[17]
Stiebitz
M. Stiebitz. Decomposing graphs under degree constraints. J. Graph Theory, 23(3):321–324, 1996
1996
-
[18]
B. D. Sullivan. A summary of problems and results related to the Caccetta-H¨ aggkvist conjec- ture, 2006
2006
-
[19]
Thomassen
C. Thomassen. Disjoint cycles in digraphs. Combinatorica, 3(3-4):393–396, 1983
1983
-
[20]
Thomassen
C. Thomassen. Graph decomposition with constraints on the connectivity and minimum degree. J. Graph Theory, 7(2):165–167, 1983
1983
-
[21]
Thomassen
C. Thomassen. Even cycles in directed graphs. European J. Combin., 6(1):85–89, 1985. 12
1985
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.