Pith. sign in

REVIEW 2 minor 1 cited by

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

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review

2026-07-03 23:36 UTC pith:5AWQ7YBM

load-bearing objection The paper establishes a polynomial-size hitting set for r-balls in K_{t,t}-induced-minor-free graphs of bounded clique number, which verifies a stronger form of the coarse separator conjecture in this class.

arxiv 2606.14974 v2 pith:5AWQ7YBM 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
classification math.CO
keywords induced minorsbicliquesbalanced separatorscoarse treewidthhereditary graph classestree decompositions
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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.

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.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

Share X LinkedIn Reddit HN

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

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.

reviewed 2026-07-03 · how reviews work

0 comments
Cite this review

Pith. "Pith review of Coarse Balanced Separators in Biclique-Induced-Minor-Free Graphs." pith.science (2026). https://pith.science/paper/5AWQ7YBM

@misc{pith2026260614974,
  author       = {Pith},
  title        = {Pith review of: Coarse Balanced Separators in Biclique-Induced-Minor-Free Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5AWQ7YBM}},
  note         = {Machine review of arXiv:2606.14974}
}
Share X LinkedIn Reddit HN
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$.

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 ↗

discussion (0)

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

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Fatness and Flatness

    math.CO 2026-07 accept novelty 7.0

    Excluding a fixed graph as a fat minor forces a metric analog of uniform quasi-wideness; this bounds scatter dimension and yields EPAS-style approximation for norm k-clustering.

Reference graph

Works this paper leans on

28 extracted references · 28 canonical work pages · cited by 1 Pith paper

  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 , volume =

    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 that are quasi-isometric to graphs with bounded treewidth

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

    work page Pith review 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

    work page

  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 =

    work page 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=

    work page 1986

  14. [14]

    Albrechtsen and J

    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]

    Dominated Balanced Separators in Wheel-Induced-Minor-Free Graphs , journal =

    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 =

    work page

  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

    work page

  23. [23]

    Dallard, M

    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=

    work page 1927

  26. [26]

    Tree-independence number

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

    work page

  27. [27]

    , author=

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

    work page 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

This paper was first reviewed by grok-4.3 on July 3, 2026.