pith. sign in

arxiv: 2606.14974 · v2 · pith:5AWQ7YBMnew · submitted 2026-06-12 · 🧮 math.CO

Coarse Balanced Separators in Biclique-Induced-Minor-Free Graphs

Maria Chudnovsky , Julien Codsi , Claire Kaneshiro This is my paper

Pith reviewed 2026-07-03 23:36 UTC · model grok-4.3

classification 🧮 math.CO
keywords induced minorsbicliquesbalanced separatorscoarse treewidthhereditary graph classestree decompositions
0
0 comments X

The pith

K_{t,t}-induced-minor-free graphs with bounded clique number admit coarse balanced separators whose size is polynomial in the clique bound.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper verifies a stronger form of the coarse balanced separator conjecture for every radius r in the hereditary class of K_{t,t}-induced-minor-free graphs whose clique number is bounded by a fixed s. For any large vertex set Y, it produces a set Z whose size is bounded by a polynomial in s such that, after deleting Z, no single ball of radius r covers a large fraction of Y. This hitting-set property directly yields the desired coarse tree decompositions whose bags are covered by a bounded number of balls of some larger radius r'. A sympathetic reader would care because the result extends the classical linear relation between treewidth and separation number to a coarse, ball-cover version inside a concrete hereditary class.

Core claim

In K_{t,t}-induced-minor-free graphs with clique number at most s, for every r and every large Ysubseteq V(G), there exists Z with |Z| bounded by a polynomial in s such that no ball of radius r in G-Z covers a large proportion of Y. This property is shown to imply that every such graph admits balanced separators coverable by a bounded number of balls of some radius r' and therefore satisfies the stronger coarse analogue of the Robertson-Seymour theorem.

What carries the argument

A polynomial-size hitting set Z for radius-r balls that cover large fractions of a given set Y, with the polynomial degree depending only on the clique-number bound s.

If this is right

  • The coarse balanced separator conjecture holds for every r inside this hereditary class.
  • Coarse tree decompositions exist in which every bag is covered by a bounded number of balls of radius r' depending on r and s.
  • The polynomial bound on the size of Z is uniform across all radii r.
  • The same hitting-set technique applies to any weight function on the vertices when constructing balanced separators.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same polynomial hitting-set construction may apply inside other hereditary classes that exclude large induced bicliques.
  • The result supplies a concrete route toward polynomial-time approximation schemes for balanced separator problems inside these graphs.
  • Removing the clique-number bound while keeping the induced-minor-free condition would require an entirely different argument.

Load-bearing premise

The input graphs are K_{t,t}-induced-minor-free and have clique number bounded by some fixed s.

What would settle it

An explicit K_{t,t}-induced-minor-free graph with clique number s, a radius r, and a set Y such that every set Z of size polynomial in s leaves some radius-r ball covering a large fraction of Y.

Figures

Figures reproduced from arXiv: 2606.14974 by Claire Kaneshiro, Julien Codsi, Maria Chudnovsky.

Figure 1
Figure 1. Figure 1: Construction of the hypergraph H. Theorem 2.4 to find a vertex in Y ⋆ that is contained in the r-neighborhood of many vertices of I ⋆ . We first show that ν(H) and λ(H) are bounded by functions of t and νD. (6) It holds that ν(H) ≤ νD. Suppose not, then there are more than νD pairwise disjoint subsets of Y ⋆ , each with at least α(Y ) νD vertices. Therefore |Y ⋆ | > α(Y ) νD · νD = α(Y ). Since Y ⋆ is an i… view at source ↗
Figure 2
Figure 2. Figure 2: Visualization of the proof of (8). (9) If k /∈ {i, j}, then for every l, Pk,l is anticomplete to si,j . Suppose that si,j is adjacent to a vertex u ∈ Pk,l. Then |l(u) − l(si,j )| = 1. First, suppose that si,j ∈ Lm−1 and u ∈ Lm for some m ∈ [r]. See the left-hand side of [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Visualization of the proof of (9). which contains a Kt,t induced minor, a contradiction. This completes the proof of (7). By (6), ν(H) ≤ νD and by (7), λ(H) ≤ 2t. Note that νD ≤ ν. By Theorem 2.4, we have τ (H) ≤ 11(2t) 2 (2t + νD + 3)  2t + νD νD 2 ≤ τ. Let T ⊆ Y ⋆ be a hitting set of minimum size. Since |T | ≤ τ , there exists a vertex x ∈ T such that the set ˜I = {z ∈ I ⋆ : x ∈ ez} has size | ˜I| ≥ 1 … view at source ↗
Figure 4
Figure 4. Figure 4: Visualization of the proof of (10). l(u) = m for some m. Since u ∈ J˜D, there exist z ′ ∈ ˜I (not necessarily distinct from z), and [PITH_FULL_IMAGE:figures/full_fig_p009_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Visualization of the induced subgraphs J1, . . . , JR given by Claim 2.8 [PITH_FULL_IMAGE:figures/full_fig_p010_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Visualization of the proof of (12). The vertices in Gˆ are distin￾guished by white fill and black outline. Since S is a balanced separator for Yˆ , we can bound |Yˆ ⋆ | as follows: |Yˆ ⋆ | ≤ |V (C) ∩ Yˆ | + |Sˆ| + |Z| + |Yˆ S| ≤ 1 2 |Yˆ | + 2k + 2f(8ks) + |Yˆ | 4 < 3|Yˆ | 4 + 3f(8ks) ≤ 12f(8ks) = |Yˆ |. Now suppose that C1, . . . , Cm are the components of G−(Z∪S). By the inductive hypothesis, for every i … view at source ↗
read the original abstract

It is a classical theorem of Robertson and Seymour (1986) that the treewidth of a graph is linearly related to its separation number: the smallest integer $k$ such that, for every weight function on the vertices, the graph admits a balanced separator of size at most $k$. Motivated by recent progress on coarse treewidth, Abrishami, Czy\.zewska, Kluk, Pilipczuk, Pilipczuk, and Rza\.zewski (2025) conjectured the following coarse analogue: for every $r\in \mathbb{N}$ there exists an $r'\in \mathbb{N}$ such that every graph that admits balanced separators that can be covered by a bounded number of balls of bounded radius $r$ admits a tree decomposition where every bag can be covered by a bounded number of balls of radius $r'$. We verify a stronger variant of this conjecture for all $r \in \mathbb{N}$ for the hereditary class of $K_{t,t}$-induced-minor-free graphs of bounded clique number. A key step in the proof is the following result, which we expect to be of independent interest. In $K_{t,t}$-induced-minor-free graphs with clique number bounded by $s$, given a large subset of vertices $Y \subseteq V(G)$, there is a set $Z$ whose size is bounded by a function polynomial in $s$, such that no ball of radius $r$ in $G- Z$ covers a large proportion of $Y$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript verifies a stronger variant of the coarse balanced-separator conjecture for every fixed r ∈ ℕ in the hereditary class of K_{t,t}-induced-minor-free graphs with clique number at most s. It shows that if such a graph admits balanced separators coverable by a bounded number of r-balls, then it admits a tree decomposition in which every bag is coverable by a bounded number of r'-balls for some r' depending on r. The key technical step is an existence result: given any large Y ⊆ V(G), there exists Z with |Z| bounded by a polynomial in s (uniformly for the fixed r) such that no r-ball in G−Z meets a large fraction of Y.

Significance. If the central claims hold, the work supplies the first non-trivial verification of the coarse balanced-separator conjecture inside a hereditary minor-closed class, together with a separator lemma that is explicitly flagged as potentially of independent interest. The polynomial dependence on the clique-number bound s (for each fixed r) yields a constant-size Z once s is fixed by the class, which is the right strength for the hereditary setting.

minor comments (2)
  1. [Abstract] The abstract states the polynomial bound on |Z| but does not record the explicit degree or its dependence on r; a short remark in §1 or the statement of the key lemma would improve readability.
  2. [Abstract] The notation K_{t,t} for the forbidden induced minor is introduced without an immediate reminder that t is the parameter defining the class while s bounds the clique number; a parenthetical clarification would avoid any momentary ambiguity.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their careful reading and positive evaluation of the manuscript. We are grateful for the recommendation to accept.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper establishes an existence theorem for a hitting set Z of polynomial size in s within the hereditary class of K_{t,t}-induced-minor-free graphs of bounded clique number, using the structural properties of the forbidden induced minor and standard separator arguments. No step reduces a claimed prediction or first-principles result to its own inputs by definition, fitted parameters, or load-bearing self-citation chains; the central claim is an independent mathematical verification of a stronger form of the coarse balanced-separator conjecture, with all dependencies external to the result itself.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The result rests on the standard definition of induced minors, the hereditary property of the class, and the classical Robertson-Seymour separator theorem; no new entities or fitted constants are introduced.

axioms (2)
  • domain assumption Every graph in the class is K_{t,t}-induced-minor-free and has clique number at most s for fixed s.
    Invoked to obtain the polynomial bound on |Z|; stated in the abstract as the setting of the theorem.
  • standard math Standard axioms of finite undirected graphs and the definition of radius-r balls and balanced separators.
    Background used throughout the statement of both the conjecture and the proved variant.

pith-pipeline@v0.9.1-grok · 5811 in / 1389 out tokens · 21131 ms · 2026-07-03T23:36:27.422898+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

28 extracted references · 20 canonical work pages

  1. [1]

    , TITLE =

    Ramsey, Frank P. , TITLE =. Proc. London Math. Soc. (2) , FJOURNAL =. 1929 , NUMBER =. doi:10.1112/plms/s2-30.1.264 , URL =

    work page doi:10.1112/plms/s2-30.1.264 1929

  2. [2]

    2017 , PAGES =

    Diestel, Reinhard , TITLE =. 2017 , PAGES =. doi:10.1007/978-3-662-53622-3 , URL =

    work page doi:10.1007/978-3-662-53622-3 2017

  3. [3]

    arXiv preprint arXiv:2505.06550 , year=

    Coarse Balanced Separators and Tree-Decompositions , author=. arXiv preprint arXiv:2505.06550 , year=

    work page arXiv

  4. [4]

    Courcelle, Bruno , TITLE =. Inform. and Comput. , FJOURNAL =. 1990 , NUMBER =. doi:10.1016/0890-5401(90)90043-H , URL =

    work page doi:10.1016/0890-5401(90)90043-h 1990

  5. [5]

    Combinatorica , FJOURNAL =

    Georgakopoulos, Agelos and Papasoglu, Panos , TITLE =. Combinatorica , FJOURNAL =. 2025 , NUMBER =. doi:10.1007/s00493-025-00150-6 , URL =

    work page doi:10.1007/s00493-025-00150-6 2025

  6. [6]

    Graphs quasi-isometric to graphs with bounded treewidth.arXiv preprint arXiv:2501.10840, 2025

    Graphs quasi-isometric to graphs with bounded treewidth , author=. arXiv preprint arXiv:2501.10840 , year=

    work page arXiv

  7. [7]

    arXiv preprint arXiv:2502.20182 , year=

    On coarse tree decompositions and coarse balanced separators , author=. arXiv preprint arXiv:2502.20182 , year=

    work page arXiv

  8. [8]

    Combinatorica , FJOURNAL =

    Ding, Guoli and Seymour, Paul and Winkler, Peter , TITLE =. Combinatorica , FJOURNAL =. 1994 , NUMBER =. doi:10.1007/BF01305948 , URL =

    work page doi:10.1007/bf01305948 1994

  9. [9]

    Asymptotic structure

    Nguyen, Tung and Scott, Alex and Seymour, Paul , journal=. Asymptotic structure

  10. [10]

    European J

    Lozin, Vadim and Razgon, Igor , TITLE =. European J. Combin. , FJOURNAL =. 2022 , PAGES =. doi:10.1016/j.ejc.2022.103517 , URL =

    work page doi:10.1016/j.ejc.2022.103517 2022

  11. [11]

    Bourneuf, Romain and Buci\'c, Matija and Cook, Linda and Davies, James , TITLE =. Adv. Comb. , FJOURNAL =. 2024 , PAGES =

    2024

  12. [12]

    Tree independence number

    Chudnovsky, Maria and Codsi, Julien and Lokshtanov, Daniel and Milani. Tree independence number. arXiv preprint arXiv:2501.14658 , year=

    work page arXiv

  13. [13]

    , journal=

    Robertson, Neil and Seymour, Paul D. , journal=. Graph minors. 1986 , publisher=

    1986

  14. [14]

    arXiv preprint arXiv:2508.15342 , year=

    Counterexample to the conjectured coarse grid theorem , author=. arXiv preprint arXiv:2508.15342 , year=

    work page arXiv

  15. [15]

    Nguyen, Tung and Scott, Alex and Seymour, Paul , TITLE =. J. Combin. Theory Ser. B , FJOURNAL =. 2025 , PAGES =. doi:10.1016/j.jctb.2025.01.004 , URL =

    work page doi:10.1016/j.jctb.2025.01.004 2025

  16. [16]

    Combinatorica , FJOURNAL =

    Berger, Eli and Seymour, Paul , TITLE =. Combinatorica , FJOURNAL =. 2024 , NUMBER =. doi:10.1007/s00493-024-00088-1 , URL =

    work page doi:10.1007/s00493-024-00088-1 2024

  17. [17]

    arXiv preprint arXiv:2512.12329 , year=

    Dominated balanced separators in wheel-induced-minor-free graphs , author=. arXiv preprint arXiv:2512.12329 , year=

    work page arXiv

  18. [18]

    Robertson, Neil and Seymour, P. D. , TITLE =. J. Combin. Theory Ser. B , FJOURNAL =. 1986 , NUMBER =. doi:10.1016/0095-8956(86)90030-4 , URL =

    work page doi:10.1016/0095-8956(86)90030-4 1986

  19. [19]

    Quasi-Polynomial Time Techniques for Independent Set and Beyond in Hereditary Graph Classes , author =

  20. [20]

    Quasi-polynomial time approximation schemes for the maximum weight independent set problem in

    Chudnovsky, Maria and Pilipczuk, Marcin and Pilipczuk, Micha. Quasi-polynomial time approximation schemes for the maximum weight independent set problem in. SIAM J. Comput. , FJOURNAL =. 2024 , NUMBER =. doi:10.1137/20M1333778 , URL =

    work page doi:10.1137/20m1333778 2024

  21. [21]

    Chudnovsky, Maria and Hajebi, Sepehr and Lokshtanov, Daniel and Spirkl, Sophie , TITLE =. J. Combin. Theory Ser. B , FJOURNAL =. 2026 , PAGES =. doi:10.1016/j.jctb.2025.08.003 , URL =

    work page doi:10.1016/j.jctb.2025.08.003 2026

  22. [22]

    Induced subgraphs and tree decompositions

    Chudnovsky, Maria and Gartland, Peter and Hajebi, Sepehr and Lokshtanov, Daniel and Spirkl, Sophie , journal=. Induced subgraphs and tree decompositions

  23. [23]

    Treewidth versus clique number

    Dallard, Cl\'. Treewidth versus clique number. J. Combin. Theory Ser. B , FJOURNAL =. 2024 , PAGES =. doi:10.1016/j.jctb.2024.03.005 , URL =

    work page doi:10.1016/j.jctb.2024.03.005 2024

  24. [24]

    Robertson, Neil and Seymour, P. D. , TITLE =. J. Combin. Theory Ser. B , FJOURNAL =. 1983 , NUMBER =. doi:10.1016/0095-8956(83)90079-5 , URL =

    work page doi:10.1016/0095-8956(83)90079-5 1983

  25. [25]

    Fundamenta Mathematicae , volume=

    Zur allgemeinen Kurventheorie , author=. Fundamenta Mathematicae , volume=. 1927 , pages=

    1927

  26. [26]

    Tree-independence number

    Chudnovsky, Maria and Codsi, Julien , journal=. Tree-independence number

  27. [27]

    , author=

    Asymptotic bounds for bipartite Ramsey numbers. , author=. The Electronic Journal of Combinatorics [electronic only] , volume=. 2001 , publisher=

    2001

  28. [28]

    , TITLE =

    Bodlaender, Hans L. , TITLE =. Automata, languages and programming (. 1988 , ISBN =. doi:10.1007/3-540-19488-6\_110 , URL =

    work page doi:10.1007/3-540-19488-6 1988