Induced Minors and Coarse Tree Decompositions
Pith reviewed 2026-05-15 12:31 UTC · model grok-4.3
The pith
Graphs excluding K_{t,t} and the grid as induced minors have tree decompositions where each bag has distance 16(log n +1)-independence number at most c(log n)^d.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
We prove that for every positive integer t there exist positive integers c and d such that every graph G excluding both K_{t,t} and the grid as an induced minor has a tree decomposition in which every bag has distance 16(log n +1)-independence number at most c(log n)^d. We also prove a version of the claim in which every bag has distance-8 independence number at most 2^{c (log n)^{1-(1/d)}}.
What carries the argument
A tree decomposition of the graph in which the distance-r independence number of each bag is bounded, with r set to 16(log n +1) to obtain the polylogarithmic size bound.
If this is right
- Dynamic programming or other algorithms on these graphs can process each bag with only polylogarithmic overhead.
- The original conjecture would follow if the distance parameter can be reduced to 1 while preserving the same size bound.
- A related decomposition exists for fixed distance 8 with a bound that is exponential in a subpolynomial power of log n.
Where Pith is reading between the lines
- Varying the distance parameter may allow the full conjecture to be proved for wider families of forbidden induced minors.
- The decompositions could link to bidimensionality techniques and produce subexponential algorithms for problems on these graph classes.
- Determining the smallest distance that still yields a polylog bound would clarify how much relaxation is essential.
Load-bearing premise
The input graph must exclude both K_{t,t} and the grid as induced minors; without this exclusion the bounded decomposition is not guaranteed to exist.
What would settle it
A graph that excludes both K_{t,t} and the grid as induced minors, yet every tree decomposition has some bag whose distance 16(log n +1)-independence number exceeds every polylogarithmic function of n.
read the original abstract
Let $G$ be a graph, $S \subseteq V(G)$ be a vertex set in $G$ and $r$ be a positive integer. The distance $r$-independence number of $S$ is the size of the largest subset $I \subseteq S$ such that no pair $u$, $v$ of vertices in $I$ have a path on at most $r$ edges between them in $G$. It has been conjectured [Chudnovsky et al., arXiv, 2025] that for every positive integer $t$ there exist positive integers $c$, $d$ such that every graph $G$ that excludes both the complete bipartite graph $K_{t,t}$ and the grid $\boxplus_t$ as an induced minor has a tree decomposition in which every bag has (distance $1$) independence number at most $c(\log n)^d$. We prove a weaker version of this conjecture where every bag of the tree decomposition has distance $16(\log n + 1)$-independence number at most $c(\log n)^d$. On the way we also prove a version of the conjecture where every bag of the decomposition has distance $8$-independence number at most $2^{c (\log n)^{1-(1/d)}}$.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proves a weaker version of the conjecture by Chudnovsky et al. that graphs excluding both K_{t,t} and the t-grid as induced minors admit a tree decomposition in which every bag has distance-1 independence number at most c(log n)^d. The authors establish the same polynomial-logarithmic bound but for the distance-16(log n + 1) independence number of each bag, together with an auxiliary result bounding the distance-8 independence number by 2^{c (log n)^{1-1/d}}.
Significance. The result supplies concrete progress toward the conjecture by delivering an explicit coarse tree decomposition whose bags have polynomially logarithmic independence number at a logarithmic distance. The self-contained combinatorial argument, which directly tracks the distance-r independence number through the construction without auxiliary parameters, is a clear strength and may serve as a foundation for tightening the distance to a constant.
minor comments (3)
- [§2] §2, Definition 2.3: the distance-r independence number is introduced via a path-length condition; a short sentence clarifying that the paths are taken in the whole graph G (not inside the bag) would prevent misreading when the definition is reused in the decomposition construction.
- [Theorem 1.2] Theorem 1.2 and the auxiliary statement: the dependence of the constants c and d on the excluded-minor parameter t is stated but not quantified; adding an explicit (even non-constructive) dependence would strengthen the result statement.
- [§4] Figure 1 (if present) or the schematic in §4: the illustration of the recursive bag construction would benefit from labeling the distance scaling at each recursion level to match the 16(log n + 1) bound derived in the text.
Simulated Author's Rebuttal
We thank the referee for the positive report and recommendation of minor revision. We agree with the summary that the manuscript establishes a weaker form of the Chudnovsky et al. conjecture, replacing the distance-1 independence number bound with a distance-16(log n + 1) bound while retaining the polynomial-logarithmic size, together with the stated auxiliary result on distance-8 independence number.
Circularity Check
No significant circularity; self-contained combinatorial proof
full rationale
The paper states the conjecture from prior work (Chudnovsky et al. 2025) only as context and then directly proves a strictly weaker statement via an explicit construction of the coarse tree decomposition. This construction tracks the distance-16(log n + 1) independence number of bags and derives the c(log n)^d bound from the K_{t,t} and grid induced-minor exclusions using standard minor-closed properties. No equation or claim reduces by construction to a fitted parameter, renamed empirical pattern, or load-bearing self-citation; all steps are parameter-free and externally falsifiable. The additional distance-8 version is likewise derived directly. This is the normal case of an independent combinatorial argument.
Axiom & Free-Parameter Ledger
axioms (1)
- standard math Standard definitions and basic properties of induced minors, tree decompositions, and distance-r independence numbers hold in finite graphs.
Forward citations
Cited by 1 Pith paper
-
Coarse Balanced Separators in Fat-Minor-Free Graphs
Graphs excluding any fixed H as a d-fat minor admit balanced separators coverable by O(n^{1/2+ε}) radius-r balls, with a poly-time algorithm to find the separator or the fat model.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.