Pith. sign in

REVIEW 2 major objections 3 minor 34 references

Length spaces that exclude a fixed graph as a delta-fat minor are drill-flat: every large point set contains a sizable subset that becomes alpha-scattered after deleting a bounded number of beta-balls, provided beta is at least about sqrt(a

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 · deepseek-v4-flash

2026-08-01 07:20 UTC pith:WENF6J54

load-bearing objection Real advance in fat-minor-free metric structure, but the central iteration has a systematic 10h-vs-10^h exponent error that must be fixed before the proof is reproducible. the 2 major comments →

arxiv 2607.21474 v1 pith:WENF6J54 submitted 2026-07-23 math.CO cs.DMcs.DSmath.MG

Fatness and Flatness

Arnold Filtser , Hung Le , Nikolas M\"ahlmann , Marcin Pilipczuk , Micha{\l} Pilipczuk This is my paper
classification math.CO cs.DMcs.DSmath.MG MSC 05C8305C1268W25
keywords fat minorsdrill-flatnessshallow induced minorsepsilon-scatter dimensionk-clustering approximationhereditary graph classesmetric graph theorysubdivided cliques and webs
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 establishes a metric analogue of a central structural dichotomy. It shows that a length space excluding a fixed graph as a 'fat minor' — a minor whose branch sets are forced to be far apart — must be 'drill-flat': every sufficiently large set of points contains a sizable subset that becomes mutually far apart once a bounded number of small balls are removed. This removes a barrier to transferring minor-based structure to metric spaces, and yields the first approximation algorithms for general fat-minor-free clustering. In hereditary unweighted graph classes the paper goes further and characterizes drill-flatness exactly by the absence of shallow induced minors, equivalently by the absence of certain subdivided cliques and webs — an induced-minor analogue of the known equivalence between flatness and nowhere denseness.

Core claim

The central claim, Theorem 1.2, is quantitative: for fixed h and positive alpha, delta, if beta >= 25 sqrt(alpha delta), then any length space excluding K_h as a 2alpha-shallow delta-fat minor is (alpha,beta)-drill-flat, with overhead roughly m^{2^{O(h alpha/beta)}} and budget O(h alpha/beta). The proof only uses exclusion of shallow fat minors, so it is stronger than excluding ordinary fat minors. A corollary is that (epsilon,r)-scatters have bounded order whenever r is at least c*delta, with c = O(1/epsilon^2). That bound feeds into a parameterized approximation scheme for NORM k-clustering (k-center, k-median, k-means) with guarantee (1+epsilon)OPT + O(delta/epsilon^2)||1||. In hereditary

What carries the argument

A delta-fat minor of H in a length space is a drawing of the vertices and edges of H as arc-connected branch sets whose non-incident pieces are pairwise at least delta apart; '2alpha-shallow' requires these branch sets to have radius at most 2alpha. Drill-flatness names the paper's target: every large A contains a size m subset B that becomes alpha-scattered after deleting at most s balls of radius beta. The proof engine is an improvement dichotomy (Lemmas 4.1 and 4.2): from a large 1-scattered set that does not improve to 1+epsilon scatter by drilling few balls, a dense auxiliary graph of shortest paths yields a shallow delta-fat K_h; excluding K_h forces the improvement, and iterating it a

Load-bearing premise

For the metric theorem, the load-bearing premise is the scaling condition beta >= 25 sqrt(alpha delta), because the hole-enlargement step can otherwise consume the entire gain in scatteredness; for the equivalence theorem, the additional load-bearing premise is heredity, which the paper shows is genuinely necessary since non-hereditary classes can be drill-flat while containing all graphs as induced subgraphs.

What would settle it

Construct a length space that excludes K_h as a 2alpha-shallow delta-fat minor but fails (alpha,beta)-drill-flatness for some beta < 25 sqrt(alpha delta): for example, a space where every large A has no sizable subset that becomes alpha-scattered after deleting any bounded number of beta-balls. Equivalently for the algorithmic corollary, exhibit such a space whose (epsilon,r)-scatter order is unbounded for r just above c*delta; either example would pinpoint where the theorem's quantitative threshold is tight.

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

If this is right

  • A metric graph excluding a fixed H as a delta-fat minor is (alpha,beta)-drill-flat whenever beta >= 25 sqrt(alpha delta), with overhead and budget controlled by h and alpha/beta.
  • For any epsilon in (0,1), (epsilon,r)-scatters in such spaces have bounded order once r is at least O(delta/epsilon^2).
  • NORM k-clustering instances on delta-fat-minor-free spaces admit (1+epsilon)-approximations with additive O(delta/epsilon^2)||1||, covering k-center, k-median, and k-means.
  • In hereditary graph classes, drill-flatness is equivalent to induced-shallow-minor-freeness, fat-shallow-minor-freeness, and the exclusion of K(r,n) and W(r,n) as induced subgraphs for every r>=3.
  • Intersection graphs of balls in R^d are induced-shallow-minor-free for every d, hence drill-flat.

Where Pith is reading between the lines

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

  • If the open question whether beta = Omega(delta) suffices is answered positively, the scatter threshold r >= c*delta would drop to c = O(1/epsilon) and the additive clustering error to O(delta/epsilon)||1||; this is an extrapolation from the paper's own conjecture, not a proved consequence.
  • The proof technique, which avoids model-theoretic branching arguments in favor of extremal density, is likely to carry other minor-free coarse geometry results such as separator statements into fat-minor-free metric spaces.
  • The hereditary characterization suggests an algorithmic test: for a fixed r, deciding whether a class contains arbitrarily large K(r,n) or W(r,n) would certify failure of drill-flatness; the dichotomy makes small r worth testing first.

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

2 major / 3 minor

Summary. The paper introduces drill-flatness, a metric analogue of graph flatness (uniform quasi-wideness), and proves three groups of results. First, in the setting of length spaces, it shows that any length space excluding a fixed graph as a shallow δ-fat minor is (α,β)-drill-flat, with explicit bounds on the overhead and budget (Theorem 1.2). From this it derives a bound on ε-scatter dimension at scales large compared to δ (Theorem 1.3) and, using the framework of Abbasi et al., an EPAS-type approximation for NORM k-CLUSTERING with an additive O(δ/ε²) term (Theorem 1.4). Second, for hereditary graph classes, it proves an induced-minor characterization: induced-shallow-minor-freeness, fat-shallow-minor-freeness, drill-flatness, and excluding certain subdivided cliques and webs are equivalent (Theorem 1.6). Third, it shows that intersection graphs of balls in R^d are induced-shallow-minor-free (Theorem 1.7). The proofs are largely self-contained, building on iterative scattering-improvement lemmas, Ramsey arguments, and fat-minor construction lemmas.

Significance. If the technical issue discussed below is resolved, this is a substantial contribution. Theorem 1.2 appears to be the first metric analogue of the flatness/nowhere-denseness connection for fat-minor-free length spaces, and it yields concrete algorithmic consequences for clustering that were previously unknown in this generality. The induced-minor characterization in Theorem 1.6 is clean and unifies several known notions, with the hereditary caveat correctly identified. The paper is also honest about its limitations, explicitly leaving open the β=Ω(δ) strengthening and the sharp bound on c in Theorem 1.3. The proofs are written in full, with explicit bounds, and the exposition is generally careful. The main obstacle to accepting the current version is the exponent error in the central iteration of Section 4, which is load-bearing but appears locally fixable.

major comments (2)
  1. [§4.2, Lemma 4.2] The stopping argument is not valid as written. The proof correctly observes that after a first-outcome step |A_{i+1}| > |A_i|^{1/10}, so |A_i| ≥ |A|^{10^{-i}}. But with (18) as printed, |A| ≥ C^{10h} gives |A_h| ≥ C^{10h/10^h}, which does not imply |A_h| ≥ h. The line “From (18), we infer … |A_i| ≥ max(...)^{10h−i}” is incompatible with the earlier recurrence; it would follow only if (18) were C^{10^h}. Therefore the appeal to Lemma 3.2, and the contradiction that forces the second outcome, are unsupported. Since the final bound N(m) ≤ m^{2^{O(hα/β)}} is exactly what one obtains from exponents 10^h and 10^{hk}, the fix is local, but it must be carried through the proof.
  2. [§4.2, proof of Theorem 1.2] The iterative step also mismatches exponents. Lemma 4.2 is invoked with m' = m^{10h(k−i−1)}; the stated hypothesis of Lemma 4.2 would require |A_i| ≥ (m')^{10h} = m^{100h²(k−i−1)}, whereas the invariant only gives |A_i| ≥ m^{10h(k−i)}. Even accepting Lemma 4.2's displayed statement, its second outcome produces |B| ≥ |A_i|^{1/10}, not |B| ≥ |A_i|^{1/(10h)}, so the invariant cannot be maintained as written. Replacing the exponents by 10^h and 10^{hk} fixes the arithmetic and still yields the stated final bounds; please correct every dependent occurrence, including the definitions of N(m), m', and the size invariant.
minor comments (3)
  1. [§5.2, proof of Theorem 1.4] “Without loss of generality we may assume that ε<0” is surely a typo; ε is a positive approximation parameter. The intended assumption is presumably ε∈(0,1).
  2. [§1 and §5.1] Terminology is inconsistent: Definition 1.1 uses “overhead” and “budget,” while Lemma 5.4 speaks of “wideness N and margin s.” Please align the terminology.
  3. [§4] The notation “10h”, “10hk”, and “10h−i” is ambiguous. If double-exponential exponents are intended, write 10^h, 10^{hk}, and 10^{h−i} explicitly. This is not merely cosmetic: the ambiguity is directly tied to the major issue above.

Circularity Check

0 steps flagged

No load-bearing circularity: the central drill-flatness derivation is self-contained; score reflects only minor non-load-bearing self-citations.

full rationale

The derivation chain is not circular. Theorem 1.2 is obtained by iterating Lemmas 4.1/4.2, which build shallow fat minors from distance configurations via Lemmas 3.1/3.2; drill-flatness is the output, not an input. Theorem 1.3 combines Theorem 1.2 with Lemma 5.4, which is stated and proved in full in Section 5.1; the remark that its proof is essentially [8, Lemma 4.1] is a proof-scheme attribution, not a black-box import. [8] is by a co-author, but the lemma is independently reproduced here. Theorem 2.1 is cited from [30, Corollary 2.3] (also co-authored), but it is a corollary of the external Alon-Krivelevich-Sudakov theorem, so it is independent support. Part II's Theorem 1.6 is a genuine cycle of implications with nontrivial lemmas (Lemma 7.1 derives FSMF from drill-flatness via fatness; Lemma 8.6 uses Ramsey/fan arguments); the definitions are not rigged so the equivalences hold by construction. No fitted parameter is renamed as a prediction; the algorithmic consequence feeds [1] with a derived scatter-dimension bound. I did not find a circular step. Separately, there is a non-circular correctness concern in Lemma 4.2: the text says 'From (18), we infer that for every 0⩽i⩽h we have |Ai|⩽(max(...))^{10h−i}', whereas Lemma 4.1's first outcome only guarantees |A_{i+1}|>|A_i|^{1/10}; this looks like an exponent-tracking error (possibly the intended exponent is 10^h), not a circularity. The explicit open question about whether β=Ω(δ) suffices is itself evidence that the theorem is not hiding its conclusion in an assumption.

Axiom & Free-Parameter Ledger

0 free parameters · 5 axioms · 0 invented entities

No numbers are fitted to data; all constants and ratios are universal proof parameters. The new named objects (drill-flatness, r-subdivided cliques, r-webs, bipartite patterns) are internal mathematical definitions, not postulated empirical entities.

axioms (5)
  • domain assumption The input is a length space and drilling out a set Z yields a length space G-Z with distances defined by Z-avoiding paths.
    Used throughout Part I to define scatteredness after deletion and to construct branch sets from paths; stated in Section 2.2.
  • standard math Alon-Krivelevich-Sudakov extremal theorem (Theorem 2.1): dense graphs contain K_h as a 1-shallow minor.
    Central for extracting K_h from dense auxiliary graphs in Lemma 4.1 and Lemma 6.1.
  • standard math Ramsey's theorem.
    Used in the fan lemma (Lemma 8.4) and in Lemma 8.6 to homogenize path lengths and cross-path edge patterns.
  • domain assumption Every graph is an induced minor of a sufficiently large 1-subdivision of a clique.
    Used to reduce ISMF to excluding a 1-subdivision of K_h in Theorem 1.5 and the (1)->(3) implication of Theorem 1.6.
  • domain assumption Abbasi et al. EPAS theorem (Theorem 5.3): bounded epsilon-scatter dimension implies an EPAS for NORM k-clustering.
    External algorithmic black box used in Theorem 1.4 to convert the scatter-dimension bound into an approximation algorithm.

pith-pipeline@v1.3.0-alltime-deepseek · 37387 in / 20016 out tokens · 191903 ms · 2026-08-01T07:20:16.057017+00:00 · methodology

0 comments
read the original abstract

Fat minors are the metric analog of graph minors that are tailored to the analysis of metric (edge-weighted) graphs and, more generally, metric spaces having a suitable notion of shortest paths. Despite a large interest in this notion, not much is known about the structure of metric graphs excluding a fixed fat minor. We prove that if a metric graph $G$ excludes a fixed graph $H$ as a $\delta$-fat minor, for some $\delta>0$, then $G$ enjoys the metric analog of flatness (aka uniform quasi-wideness) - a structural property from the field of Sparsity. In essence, our flatness result says that for any $\alpha\geq \beta$ large enough compared to $\delta$, in every large enough set $A$ in $G$ one can find a sizable subset $B$ that becomes $\alpha$-scattered after removing a bounded number of balls of radius $\beta$. We call this property drill-flatness. Notably, the proof only relies on excluding shallow fat minors: every branch set has radius at most $2\alpha$. As a corollary, we prove that metric graphs that exclude a fixed $\delta$-fat minor have bounded $\varepsilon$-scatter dimension if we consider only $\varepsilon$-scatters at distances large enough compared to $\delta$. By combining this with the results of Abbasi et al. [FOCS 2023], we infer that the $k$-Center problem on instances excluding $H$ as a $\delta$-fat minor admits an approximation algorithm that finds a solution of cost at most $(1+\varepsilon)\cdot\mathsf{OPT}+{\cal O}(\delta/\varepsilon^2)$ in time ${\cal O}_{H,\varepsilon}(n^{{\cal O}(1)})$. This is one of the first algorithmic results for general fat-minor-free metrics. We also study drill-flatness in hereditary classes of (unweighted) graphs, where we obtain a characterization equating drill-flatness with excluding shallow induced minors. This is an induced analog of the equivalence between flatness and nowhere denseness - one of central results of Sparsity.

Figures

Figures reproduced from arXiv: 2607.21474 by Arnold Filtser, Hung Le, Marcin Pilipczuk, Micha{\l} Pilipczuk, Nikolas M\"ahlmann.

Figure 1
Figure 1. Figure 1: K(3, 5) and W(3, 5). Replicated from [13]. sufficiently large patterns contain fat minors of all n-vertex graphs. Finally, implication (4)⇒(1) relies on finding large patterns within induced models of large subdivided bicliques using Ramsey’s Theorem. Examples of induced-shallow-minor-free (ISMF) classes. ISMF classes seem to fill a natural gap in the theory of hereditary graph classes, as they unify two o… view at source ↗
Figure 2
Figure 2. Figure 2: a ( 1 2 − ξ − δ, 2ξ + δ)-shallow δ-fat minor model of G constructed from f : V(H) ∪ E(H) → G − Z in Lemma 3.1. The small balls (centered at f (e)) have radius 1 2 − ξ − δ, while the large balls (centered at f (v)) have radii at most 1 2 − ξ − δ. • For every two distinct vertices u, v ∈ V(H), we have distG−Z (f (u), f (v)) > 1. • For every two distinct edges e1 , e2 ∈ E(H), we have distG−Z (f (e1 ), f (e2 )… view at source ↗
Figure 3
Figure 3. Figure 3: Two scattered sets A1 and A2 in Lemma 3.2. Each highlighted blue path has length at most 1/2 + ξ. • p x1 ,x2 2 is the last point encountered on P x1 ,x2 when traversing from x1 to x2 that satisfies distG−Z (x1 , p x1 ,x2 2 ) = 1 2 − 3ξ − δ. Such points always exist, because distG−Z (x1 , x2 ) > 1 2 −ξ and δ ⩽ ξ ⩽ 1 10 ensures that 1 2 −3ξ−2δ ⩾ 0. By the construction, points x1 , p x1 ,x2 1 , p x1 ,x2 2 , x… view at source ↗
Figure 4
Figure 4. Figure 4: Splitting P x1 ,x2 into subpaths P x1 ,x2 1 , P x1 ,x2 E , and P x1 ,x2 2 . By the choice of p x1 ,x2 1 , all points of P x1 ,x2 1 are within distance 1 2 − 3ξ − 2δ from x1 in G − Z, that is, P x1 ,x2 1 ⊆ BallG−Z (x1 , 1 2 − 3ξ − 2δ). (5) By the choice of p x1 ,x2 2 , no vertex of P x1 ,x2 1 lies within distance less than 1 2 − 3ξ − δ of x1 . Hence, for every x1 ∈ A1 and every (not necessarily distinct) x2… view at source ↗
Figure 5
Figure 5. Figure 5: P2 intersects Ball(x,ρ) at a point y. As profb1 [x] = profb2 [x] and this value is finite due to distG(b2 , x) ⩽ 2r, it follows that distG(b1 , x) ⩽ distG(b2 , x) + ρ. (24) By combining (23) and (24), we conclude that distG(a1 , b1 ) ⩽ distG(b1 , x) + distG(x, a1 ) ⩽ distG(b2 , x) + ρ + distG(x, a1 ) ⩽ r + 3ρ = (1 + ϵ)r. This is a contradiction with a1 , . . . , aℓ and b1 , . . . , bℓ being an (ϵ,r)-scatte… view at source ↗
Figure 6
Figure 6. Figure 6: gives an overview of the proof of Theorem 1.6. (1) ISMF (3) drill-flat (2) FSMF (4) no K(r, k) and W(r, k) Theorem 1.5 Lemma 7.1 Lemma 9.1 Lemma 8.1 [PITH_FULL_IMAGE:figures/full_fig_p024_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Left: K(6, 5). Right: W(6, 5). Middle: the graph H highlighted in both K(6, 5) and W(6, 5) as a 2-shallow 2-fat minor. Red branch sets model the edges of H (the four middle subdivision vertices of an edge), blue branch sets model the vertices of H (stars centered at the principal vertices); branch sets of an incident edge and vertex share a single vertex. 24 [PITH_FULL_IMAGE:figures/full_fig_p026_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: K(4, 3, 3), W(4, 3, 3), and M(4, 3, 3). Observe that asymptotically, it does not matter whether we exhibit patterns or bipartite patterns. Observation 1. Fix r ⩾ 3 and n, m ∈ N. Patterns contain bipartite patterns: 1. K(r, n + m) contains K(r, n, m) as an induced subgraph. 2. W(r, n + m) contains W(r, n, m) as an induced subgraph. Bipartite patterns contain patterns: 3. K(r, n, [PITH_FULL_IMAGE:figures/fu… view at source ↗
Figure 9
Figure 9. Figure 9: (Left) paths from γ(z) to {γ( yi )} 3 i=1 in G. (Right) the ball Bb contains {B ′ yi } 3 i=1 . Let {Bu : u ∈ V(G)} be a family of balls in R d such that Bu and Bv intersect if and only if u and v are adjacent in G. By enlarging the balls slightly, we may assume that the balls Bu have pairwise different radii. For every x ∈ V(Kh ), we define γ(x) ∈ φ(x) as the vertex of φ(x) such that the ball Bγ(x) has the… view at source ↗

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

34 extracted references · 7 linked inside Pith

  1. [1]

    Parameterized approximation schemes for clustering with general norm objectives

    Fateme Abbasi, Sandip Banerjee, Jarosław Byrka, Parinya Chalermsook, Ameet Gadekar, Kam- yar Khodamoradi, Dániel Marx, Roohani Sharma, and Joachim Spoerhase. Parameterized approximation schemes for clustering with general norm objectives. In2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023, pages 1377–1399, 2023. 35

    2023

  2. [2]

    Interpreting nowhere dense graph classes as a classical notion of model theory .European Journal of Combinatorics, 36:322–330, 2014

    Hans Adler and Isolde Adler. Interpreting nowhere dense graph classes as a classical notion of model theory .European Journal of Combinatorics, 36:322–330, 2014

    2014

  3. [3]

    Counterexample to the conjectured coarse grid theorem

    Sandra Albrechtsen and James Davies. Counterexample to the conjectured coarse grid theorem. CoRR, abs/2508.15342, 2025

    arXiv 2025

  4. [4]

    Small counterexamples to the fat minor conjecture.CoRR, abs/2601.05761, 2026

    Sandra Albrechtsen, Marc Distel, and Agelos Georgakopoulos. Small counterexamples to the fat minor conjecture.CoRR, abs/2601.05761, 2026

    arXiv 2026

  5. [5]

    Turán numbers of bipartite graphs and related ramsey-type questions.Combinatorics, Probability and Computing, 12(5-6):477–494, 2003

    Noga Alon, Michael Krivelevich, and Benny Sudakov. Turán numbers of bipartite graphs and related ramsey-type questions.Combinatorics, Probability and Computing, 12(5-6):477–494, 2003

    2003

  6. [6]

    A separator theorem for nonplanar graphs

    Noga Alon, Paul Seymour, and Robin Thomas. A separator theorem for nonplanar graphs. Journal of the American Mathematical Society, 3(4):801–808, 1990

    1990

  7. [7]

    Twin-width I: tractable FO model checking.Journal of the ACM, 69(1):1–46, 2021

    Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width I: tractable FO model checking.Journal of the ACM, 69(1):1–46, 2021

    2021

  8. [8]

    Bounding ϵ-scatter dimension via metric sparsity

    Romain Bourneuf and Marcin Pilipczuk. Bounding ϵ-scatter dimension via metric sparsity. In2025 Annual ACM-SIAM Symposium on Discrete Algorithm, SODA 2025, pages 3155–3171, 2025

    2025

  9. [9]

    Coarse balanced separators in biclique- induced-minor-free graphs.CoRR, abs/2606.14974, 2026

    Maria Chudnovsky , Julien Codsi, and Claire Kaneshiro. Coarse balanced separators in biclique- induced-minor-free graphs.CoRR, abs/2606.14974, 2026

    Pith/arXiv arXiv 2026

  10. [10]

    S., and Daniel Lokshtanov

    Maria Chudnovsky , Julien Codsi, Ajaykrishnan E. S., and Daniel Lokshtanov. Induced minors and coarse tree decompositions.CoRR, abs/2603.11379, 2026

    Pith/arXiv arXiv 2026

  11. [11]

    Coarse balanced separators and tree- decompositions.CoRR, abs/2505.06550, 2025

    Maria Chudnovsky and Robert Hickingbotham. Coarse balanced separators and tree- decompositions.CoRR, abs/2505.06550, 2025

    Pith/arXiv arXiv 2025

  12. [12]

    Fat minors cannot be thinned (by quasi-isometries).Analysis and Geometry in Metric Spaces, 14(1):20250036, 2026

    James Davies, Robert Hickingbotham, Freddie Illingworth, and Rose McCarty . Fat minors cannot be thinned (by quasi-isometries).Analysis and Geometry in Metric Spaces, 14(1):20250036, 2026

    2026

  13. [13]

    First-order model checking on monadically stable graph classes

    Jan Dreier, Ioannis Eleftheriadis, Nikolas Mählmann, Rose McCarty, Michał Pilipczuk, and Szymon Toru´nczyk. First-order model checking on monadically stable graph classes. InIEEE 65th Annual Symposium on Foundations of Computer Science, FOCS 2024, pages 21–30. IEEE, 2024

    2024

  14. [14]

    Indiscernibles and flatness in monadically stable and monadically NIP classes

    Jan Dreier, Nikolas Mählmann, Sebastian Siebertz, and Szymon Toru´nczyk. Indiscernibles and flatness in monadically stable and monadically NIP classes. In50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, volume 261 ofLIPIcs, pages 125:1–125:18. Schloss Dagstuhl — Leibniz-Zentrum für Informatik, 2023

    2023

  15. [15]

    Flip-breakability: A combinatorial dichotomy for monadically dependent graph classes

    Jan Dreier, Nikolas Mählmann, and Szymon Toru´nczyk. Flip-breakability: A combinatorial dichotomy for monadically dependent graph classes. In56th Annual ACM Symposium on Theory of Computing, STOC 2024, pages 1550–1560. ACM, 2024

    2024

  16. [16]

    Merge-width and first-order model checking

    Jan Dreier and Szymon Toru´nczyk. Merge-width and first-order model checking. In57th Annual ACM Symposium on Theory of Computing, STOC 2025, pages 1944–1955, 2025

    2025

  17. [17]

    Extension preservation on dense graph classes

    Ioannis Eleftheriadis. Extension preservation on dense graph classes. In Jörg Endrullis and Sylvain Schmitz, editors,33rd EACSL Annual Conference on Computer Science Logic, CSL 2025, volume 326 ofLIPIcs, pages 7:1–7:21. Schloss Dagstuhl — Leibniz-Zentrum für Informatik, 2025. 36

    2025

  18. [18]

    Progressive algorithms for domination and independence

    Grzegorz Fabia´nski, Michał Pilipczuk, Sebastian Siebertz, and Szymon Toru´nczyk. Progressive algorithms for domination and independence. In36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, volume 126 ofLIPIcs, pages 27:1–27:16. Schloss Dagstuhl — Leibniz-Zentrum für Informatik, 2019. See also arXiv preprint 1811.06799

    Pith/arXiv arXiv 2019

  19. [19]

    On induced versions of Menger’s theorem on sparse graphs.CoRR, abs/2309.08169, 2023

    Peter Gartland, Tuukka Korhonen, and Daniel Lokshtanov. On induced versions of Menger’s theorem on sparse graphs.CoRR, abs/2309.08169, 2023

    Pith/arXiv arXiv 2023

  20. [20]

    Graph minors and metric spaces.Combinatorica, 45(3):33, 2025

    Agelos Georgakopoulos and Panos Papasoglu. Graph minors and metric spaces.Combinatorica, 45(3):33, 2025

    2025

  21. [21]

    Madelaine

    Fatemeh Ghasemi, Julien Grange, Mamadou Moustapha Kanté, and Florent R. Madelaine. Weakly-sparse and strongly flip-flat classes of graphs are uniformly almost-wide. In34th EACSL Annual Conference on Computer Science Logic, CSL 2026, volume 363 ofLIPIcs, pages 41:1–41:14. Schloss Dagstuhl — Leibniz-Zentrum für Informatik, 2026

    2026

  22. [22]

    On an induced version of Menger’s theorem.Electronic Journal of Combinatorics, 31(4), 2024

    Kevin Hendrey , Sergey Norin, Raphael Steiner, and Jérémie Turcotte. On an induced version of Menger’s theorem.Electronic Journal of Combinatorics, 31(4), 2024

    2024

  23. [23]

    Induced minors, asymptotic dimension, and baker’s technique.arXiv preprint arXiv:2508.06190, 2025

    Robert Hickingbotham. Induced minors, asymptotic dimension, and baker’s technique.arXiv preprint arXiv:2508.06190, 2025

    Pith/arXiv arXiv 2025

  24. [24]

    Grid induced minor theorem for graphs of small degree.Journal of Combi- natorial Theory, Series B, 160:206–214, 2023

    Tuukka Korhonen. Grid induced minor theorem for graphs of small degree.Journal of Combi- natorial Theory, Series B, 160:206–214, 2023

    2023

  25. [25]

    Induced-minor-free graphs: Separator theorem, subexponential algorithms, and improved hardness of recognition

    Tuukka Korhonen and Daniel Lokshtanov. Induced-minor-free graphs: Separator theorem, subexponential algorithms, and improved hardness of recognition. In2024 ACM-SIAM Sympo- sium on Discrete Algorithms, SODA 2024, pages 5249–5275. SIAM, 2024

    2024

  26. [26]

    Forbidden induced subgraphs for bounded shrub-depth and the expressive power of MSO

    Nikolas Mählmann. Forbidden induced subgraphs for bounded shrub-depth and the expressive power of MSO. In52nd International Colloquium on Automata, Languages, and Programming, ICALP 2025, volume 334 ofLIPIcs, pages 167:1–167:18. Schloss Dagstuhl — Leibniz-Zentrum für Informatik, 2025

    2025

  27. [27]

    Existential positive transductions of sparse graphs

    Nikolas Mählmann and Sebastian Siebertz. Existential positive transductions of sparse graphs. arXiv:2601.15890, 2026

    arXiv 2026

  28. [28]

    First order properties on nowhere dense structures.Journal of Symbolic Logic, 75(3):868–887, 2010

    Jaroslav Nešetˇril and Patrice Ossona de Mendez. First order properties on nowhere dense structures.Journal of Symbolic Logic, 75(3):868–887, 2010

    2010

  29. [29]

    Springer, 2012

    Jaroslav Nešetˇril and Patrice Ossona de Mendez.Sparsity — Graphs, Structures, and Algorithms, volume 28 ofAlgorithms and Combinatorics. Springer, 2012

    2012

  30. [30]

    On the number of types in sparse graphs

    Michał Pilipczuk, Sebastian Siebertz, and Szymon Toru´nczyk. On the number of types in sparse graphs. In33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018, pages 799–808. ACM, 2018

    2018

  31. [31]

    Stable graphs.Fundamenta Mathematicae, 100(2):101– 107, 1978

    Klaus-Peter Podewski and Martin Ziegler. Stable graphs.Fundamenta Mathematicae, 100(2):101– 107, 1978

    1978

  32. [32]

    Induced subgraphs of graphs with large chromatic number

    Alex Scott and Paul Seymour. Induced subgraphs of graphs with large chromatic number. VI. Banana trees.Journal of Combinatorial Theory, Series B, 145:487–510, 2020

    2020

  33. [33]

    Flip-width: Cops and robber on dense graphs

    Szymon Toru´nczyk. Flip-width: Cops and robber on dense graphs. InIEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023, pages 663–700. IEEE, 2023

    2023

  34. [34]

    Coarse balanced separators in fat-minor-free graphs.CoRR, abs/2604.11318, 2026

    Édouard Bonnet, Hung Le, Marcin Pilipczuk, and Michał Pilipczuk. Coarse balanced separators in fat-minor-free graphs.CoRR, abs/2604.11318, 2026. 37

    Pith/arXiv arXiv 2026