pith. sign in

arxiv: 2606.24326 · v2 · pith:WUZY26IEnew · submitted 2026-06-23 · 🧮 math.CO · cs.DM

Obstructions for Minor-Closed Classes of limiting Densities Below 3/2

Antonios Kominatos , Reem Mahmoud , Dimitrios M. Thilikos This is my paper

Pith reviewed 2026-06-25 23:51 UTC · model grok-4.3

classification 🧮 math.CO cs.DM
keywords minor-closed graph classeslimiting densitygraph minorsforbidden minorsextremal graph theoryalgorithmic graph theorygraph density
0
0 comments X

The pith

For every density threshold below 3/2, only finitely many minimal minor-closed graph classes exceed it, and they can all be listed explicitly.

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

The paper starts from the known fact that every minor-closed graph class has a rational limiting density. It then proves that, for any fixed δ below 3/2, only finitely many inclusion-minimal minor-closed classes can have limiting density strictly larger than δ. These finitely many classes are identified completely for each such δ. The finiteness directly produces an algorithm that takes any finite set of forbidden minors and either returns the exact limiting density of the corresponding minor-closed class or correctly reports that the density is at least 3/2.

Core claim

For every δ in [0, 3/2), the collection of ⊆-minimal minor-closed graph classes whose limiting density exceeds δ is finite, and this collection is completely determined.

What carries the argument

The rationality of limiting density for minor-closed classes, which partitions the possible densities into intervals separated by rationals and thereby bounds the number of minimal classes that can cross any given threshold below 3/2.

If this is right

  • Given any finite set Z of graphs whose total size is n, there is a 2^{poly(n)}-time procedure that outputs δ(excl(Z)) or reports that the value is at least 3/2.
  • All minor-closed classes with limiting density below 3/2 can be classified by successively listing the minimal ones that cross each successive rational threshold.
  • The same finiteness statement supplies a finite list of candidate obstructions for every density value in [0, 3/2).

Where Pith is reading between the lines

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

  • Above 3/2 the number of minimal classes may become infinite, suggesting a phase transition in the structure of minor-closed families at that value.
  • The explicit identification of minimal classes supplies a concrete catalogue that can be used to test conjectures about which densities are achievable by minor-closed classes.
  • The algorithmic consequence extends naturally to the problem of approximating the limiting density when the exact value is not required.

Load-bearing premise

The limiting density of any minor-closed graph class is always a rational number.

What would settle it

A single minor-closed class whose limiting density is less than 3/2 yet possesses infinitely many distinct inclusion-minimal subclasses with strictly higher density.

Figures

Figures reproduced from arXiv: 2606.24326 by Antonios Kominatos, Dimitrios M. Thilikos, Reem Mahmoud.

Figure 1
Figure 1. Figure 1: The k-daisy (left), the k-chain (center), and the k-diamond (right), when k = 4. The following is a direct consequence of the main result of Qiao and Zhan in [23]. Proposition 2.2. If a tree T has ≤ l leaves and diameter ≤ d, then |V (T)| ≤ l j d 2 k + 1. Given a graph G and a vertex v ∈ V (G) with two neighbors x and y, the dissolution of v in G is the graph obtained from G − v after adding the edge xy (i… view at source ↗
Figure 2
Figure 2. Figure 2: The 2-trees on 3 (left), 4 (center), and 5 (right) vertices. [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The sets of graphs A4, A6, A8, and A10. Observe that any edge-maximal graph in G on s vertices in Aj has exactly fj (s) edges. Also, observe that for any j ∈ {4, 6, 8, 10}, fj (j) j = 3 2 and that 0 ≤ fj (j) ≤ 15. Let G ∈ Gn for some n ∈ N. Let n1, . . . , nr be the sizes of the connected components of G and observe that 1 ≤ ni ≤ j, i ∈ [r]. Let k = ⌊n/j⌋ and observe that |E(G)| ≤ X i∈[r] fj (ni) ≤ k fj (j… view at source ↗
Figure 4
Figure 4. Figure 4: Cycle C from Lemma 3.6 where (a) two edges vivi+1 and vjvj+1 have a common neighbor xi , and where (b) each edge has a distinct neighbor outside C. It is easy to prove that every chordal, K4-minor-free, biconnected graph is a 2-tree. Moreover, since every 2-tree on n ≥ 6 vertices contains a 6-vertex 2-tree as a minor (repeatedly delete simplicial vertices until you have 6 vertices) and G minor-excludes eve… view at source ↗
Figure 5
Figure 5. Figure 5: Component C ∈ Qx from Lemma 3.9 where C is a tree (left), and where C contains a cycle Y (right). Fix x ∈ S and let Qx denote the set of components of G − S that only receive edges from x in S. Observe that, for every C ∈ Qx, the graph induced by C ∪ {x} contains K3 as a minor with x ∈ V (K3). Indeed, if C is a tree, then there exist distinct u, v ∈ V (C) such that xu, xv ∈ E(G), by (ii). Contracting the p… view at source ↗
Figure 6
Figure 6. Figure 6: An example graph G from Lemma 3.11: Components of G are split into C0 and C1. An enlargement of a component C ∈ C1 is shown to the right with examples of SC (green), Q0 C (red), and Q1 C (blue). Edges E p C , Er C , and Es C are also shown in red, blue, and green, respectively. All blue components combined form Q. Proof. Let Z ∈ Q1 C . Notice that, from Lemma 3.10, there are at most f3.10(c2, k) edges in t… view at source ↗
Figure 7
Figure 7. Figure 7: The first-order obstruction sets for the classes [PITH_FULL_IMAGE:figures/full_fig_p020_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: The second-order obstruction set for the class property [PITH_FULL_IMAGE:figures/full_fig_p022_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: The sets of graphs that, along with Z4 and Z5, depicted in [PITH_FULL_IMAGE:figures/full_fig_p023_9.png] view at source ↗
read the original abstract

Given a graph class $\mathcal{G}$, the limiting density of $\mathcal{G}$ is defined as $\delta(\mathcal{G})=\lim_{n\to\infty} \mathsf{ex}(\mathcal{G},n)/n$ where $\mathsf{ex}(\mathcal{G},n)$ is the maximum number of edges of a graph in $\mathcal{G}$ on $n$ vertices. The limiting density $\delta(\mathcal{G})$ is known to be a rational number when $\mathcal{G}$ is a minor-closed graph class. For every $\delta\in[0,\frac{3}{2})$, we prove that the set of $\subseteq$-minimal minor-closed graph classes with densities $>\delta$ is finite and we identify it completely. A consequence of our results is an algorithm that, given a finite set of graphs $\mathcal{Z}$, of total size $n$, either outputs the value of $\delta(\mathsf{excl}(\mathcal{Z}))$ or reports that $\delta(\mathsf{excl}(\mathcal{Z}))\geq \frac{3}{2}$, where $\mathsf{excl}(\mathcal{Z})$ is the class of graphs excluding the graphs in $\mathcal{Z}$ as minors. The algorithm runs in $2^{\mathsf{poly}(n)}$ time.

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 / 3 minor

Summary. The paper proves that for every δ ∈ [0, 3/2), the collection of ⊆-minimal minor-closed graph classes G with limiting density δ(G) > δ is finite, and provides a complete explicit identification of these classes. It further derives a 2^{poly(n)}-time algorithm that, given a finite set Z of graphs with total size n, either computes δ(excl(Z)) exactly or certifies that δ(excl(Z)) ≥ 3/2. The argument relies on the known rationality of limiting densities for minor-closed classes.

Significance. If the classification holds, the result supplies the first complete structural description of all minimal minor-closed classes below the 3/2 density threshold together with an explicit algorithm for density computation on minor-closed classes. The finiteness statement and the algorithmic consequence are both new and directly usable; the explicit list of minimal classes constitutes a concrete, checkable output rather than an existence proof.

minor comments (3)
  1. The statement of the main theorem (presumably Theorem 1 or the result in §3) should include an explicit reference to the background rationality theorem being invoked, so that the dependence on prior work is visible at a glance.
  2. In the description of the algorithm, the running-time exponent is stated as poly(n); a short remark clarifying whether the degree is independent of the input graphs or depends on |Z| would improve readability.
  3. The paper would benefit from a small table or diagram in the introduction that lists the identified minimal classes for a few sample values of δ (e.g., δ = 1 and δ = 1.4) to illustrate the classification.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment and recommendation to accept the manuscript. The report accurately captures the main contributions: the finiteness and explicit classification of minimal minor-closed classes with density exceeding any fixed δ < 3/2, together with the resulting 2^{poly(n)}-time algorithm for computing δ(excl(Z)).

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper's central result establishes finiteness and explicit identification of minimal minor-closed classes with limiting density >δ for δ<3/2, resting on the independently known background fact (stated in the abstract) that δ(G) is rational for minor-closed G. No equations, definitions, or self-citations in the provided text reduce the claimed finiteness or algorithmic consequence to a fitted parameter, self-referential quantity, or load-bearing self-citation chain. The derivation is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the domain assumption that limiting densities of minor-closed classes are rational; no free parameters or invented entities appear in the abstract.

axioms (1)
  • domain assumption The limiting density δ(G) is a rational number whenever G is minor-closed.
    Explicitly stated as known in the abstract and used to make the thresholds δ separate the classes into finite minimal sets.

pith-pipeline@v0.9.1-grok · 5759 in / 1382 out tokens · 41816 ms · 2026-06-25T23:51:45.026779+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

33 extracted references · 24 canonical work pages

  1. [1]

    Fomin, Ignasi Sau, and Dimitrios M

    Isolde Adler, Frederic Dorn, Fedor V. Fomin, Ignasi Sau, and Dimitrios M. Thilikos. Faster parameterized algorithms for minor containment.Theoretical Computer Science, 412(50):7018–7028, 2011.doi:10.1016/ j.tcs.2011.09.015. 26

    2011

  2. [2]

    Seymour, and Robin Thomas

    Daniel Bienstock, Neil Robertson, Paul D. Seymour, and Robin Thomas. Quickly excluding a forest.J. Comb. Theory B, 52(2):274–283, 1991.doi:10.1016/0095-8956(91)90068-U. 3

    work page doi:10.1016/0095-8956(91)90068-u 1991

  3. [3]

    Bodlaender

    Hans L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth.SIAM Journal on Computing Computing, 25(6):1305–1317, 1996. 26

    1996

  4. [4]

    Fixed-parameter tractable distances to sparse graph classes.Algorithmica, 79(1):139–158, 2017.doi:10.1007/s00453-016-0235-7

    Jannis Bulian and Anuj Dawar. Fixed-parameter tractable distances to sparse graph classes.Algorithmica, 79(1):139–158, 2017.doi:10.1007/s00453-016-0235-7. 21

    work page doi:10.1007/s00453-016-0235-7 2017

  5. [5]

    Towards tight(er) bounds for the excluded grid theorem.J

    Julia Chuzhoy and Zihan Tan. Towards tight(er) bounds for the excluded grid theorem.J. Combin. Theory Ser. B, 146:219–265, 2021.doi:10.1016/j.jctb.2020.09.010. 26

    work page doi:10.1016/j.jctb.2020.09.010 2021

  6. [6]

    Springer, Heidelberg, fourth edition, 2010.doi:10.1007/978-3-642-14279-6

    Reinhard Diestel.Graph theory, volume 173 ofGraduate Texts in Mathematics. Springer, Heidelberg, fourth edition, 2010.doi:10.1007/978-3-642-14279-6. 5 29

    work page doi:10.1007/978-3-642-14279-6 2010

  7. [7]

    Asymptotic study of subcritical graph classes.SIAM J

    Michael Drmota, Éric Fusy, Mihyun Kang, Veronika Kraus, and Juanjo Rué. Asymptotic study of subcritical graph classes.SIAM J. Discret. Math., 25(4):1615–1651, 2011.doi:10.1137/100790161. 23

    work page doi:10.1137/100790161 2011

  8. [8]

    Densities of minor-closed graph families.Electron

    David Eppstein. Densities of minor-closed graph families.Electron. J. Comb., 17(1), 2010.doi:10.37236/

    2010

  9. [9]

    Erdős and L

    P. Erdős and L. Pósa. On independent circuits contained in a graph.Canadian J. Math., 17:347–352, 1965.doi:10.4153/CJM-1965-035-8. 7

    work page doi:10.4153/cjm-1965-035-8 1965

  10. [10]

    The metamathematics of the graph minor theorem

    Harvey Friedman, Neil Robertson, and Paul Seymour. The metamathematics of the graph minor theorem. InLogic and combinatorics (Arcata, Calif., 1985), volume 65 ofContemp. Math., pages 229–261. Amer. Math. Soc., Providence, RI, 1987.doi:10.1090/conm/065/891251. 29

    work page doi:10.1090/conm/065/891251 1985

  11. [11]

    The disjoint paths problem in quadratic time.J

    Ken ichi Kawarabayashi, Yusuke Kobayashi, and Bruce Reed. The disjoint paths problem in quadratic time.J. Combin. Theory Ser. B, 102(2):424–435, 2012.doi:10.1016/j.jctb.2011.07.004. 4

    work page doi:10.1016/j.jctb.2011.07.004 2012

  12. [12]

    A note on well quasi-orderings for powersets.Inf

    Petr Jancar. A note on well quasi-orderings for powersets.Inf. Process. Lett., 72(5–6):155–160, 1999. doi:10.1016/S0020-0190(99)00149-0. 4, 6

    work page doi:10.1016/s0020-0190(99)00149-0 1999

  13. [13]

    Densities of minor-closed graph classes are rational, 2020

    Rohan Kapadia and Sergey Norin. Densities of minor-closed graph classes are rational, 2020. URL: https://arxiv.org/abs/2009.13482,arXiv:2009.13482. 3, 29

    arXiv 2020

  14. [14]

    Bakshi, A

    Tuukka Korhonen, Michal Pilipczuk, and Giannos Stamoulis. Minor containment and disjoint paths in almost-linear time. In65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024, Chicago, IL, USA, October 27-30, 2024, pages 53–61. IEEE, 2024.doi:10.1109/FOCS61266.2024.00014. 4

    work page doi:10.1109/focs61266.2024.00014 2024

  15. [15]

    Kostochka

    Alexandr V. Kostochka. Lower bound of the hadwiger number of graphs by their average degree.Comb., 4(4):307–316, 1984.doi:10.1007/BF02579141. 3

    work page doi:10.1007/bf02579141 1984

  16. [16]

    Upper bounds on the graph minor theorem

    Martin Krombholz and Michael Rathjen. Upper bounds on the graph minor theorem. InWell-quasi orders in computation, logic, language and reasoning—a unifying concept of proof theory, automata theory, formal languages and descriptive set theory, volume 53 ofTrends Log. Stud. Log. Libr., pages 145–159. Springer, Cham, 2020. [2020]©2020. URL:https://doi.org/10...

    work page doi:10.1007/978-3-030-30229-0_6 2020

  17. [17]

    Wolfgang K.W. Mader. Homomorphieeigenschaften und mittlere Kantendichte von Graphen.Math. Ann., 174:265–268, 1967. 3

    1967

  18. [18]

    Fine analysis of the quasi-orderings on the power set.Order, 18(4):339–347, 2001

    Alberto Marcone. Fine analysis of the quasi-orderings on the power set.Order, 18(4):339–347, 2001. doi:10.1023/A:1013952225669. 4, 6

    work page doi:10.1023/a:1013952225669 2001

  19. [19]

    On the critical densities of minor-closed classes.Eur

    Colin McDiarmid and Michal Przykucki. On the critical densities of minor-closed classes.Eur. J. Comb., 75:66–91, 2019. URL:https://doi.org/10.1016/j.ejc.2018.08.002, doi:10.1016/J.EJC.2018.08

    work page doi:10.1016/j.ejc.2018.08.002 2019

  20. [20]

    Thilikos

    Christophe Paul, Evangelos Protopapas, and Dimitrios M. Thilikos. Graph parameters, universal obstruc- tions, and wqo, 2023. URL:https://arxiv.org/abs/2304.03688,arXiv:2304.03688. 4, 6

    arXiv 2023

  21. [21]

    Thilikos

    Christophe Paul, Evangelos Protopapas, and Dimitrios M. Thilikos. Universal obstructions of graph parameters, 2023. URL:https://arxiv.org/abs/2304.14121,arXiv:2304.14121. 4, 6, 21

    Pith/arXiv arXiv 2023

  22. [22]

    Towards better: a motivated introduction to better-quasi-orders.EMS Surv

    Yann Pequignot. Towards better: a motivated introduction to better-quasi-orders.EMS Surv. Math. Sci., 4(2):185–218, 2017.doi:10.4171/EMSS/4-2-2. 6

    work page doi:10.4171/emss/4-2-2 2017

  23. [23]

    Relation between the number of leaves of a tree and its diameter.Czechoslovak Mathematical Journal, 72(147):365–369, 2022

    Pu Qiao and Xingzhi Zhan. Relation between the number of leaves of a tree and its diameter.Czechoslovak Mathematical Journal, 72(147):365–369, 2022. URL: https://arxiv.org/abs/1904.12150, doi:10. 21136/CMJ.2021.0149-20. 7 30

    Pith/arXiv arXiv 2022

  24. [24]

    Neil Robertson and Paul D. Seymour. Graph minors. I. excluding a forest.J. Comb. Theory B, 35(1):39–61, 1983.doi:10.1016/0095-8956(83)90079-5. 3

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

  25. [25]

    Neil Robertson and Paul D. Seymour. Graph minors. V. Excluding a planar graph.J. Combin. Theory Ser. B, 41(1):92–114, 1986.doi:10.1016/0095-8956(86)90030-4. 7

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

  26. [26]

    Neil Robertson and Paul D. Seymour. Graph minors. XIII. The disjoint paths problem.J. Combin. Theory Ser. B, 63(1):65–110, 1995.doi:10.1006/jctb.1995.1006. 4

    work page doi:10.1006/jctb.1995.1006 1995

  27. [27]

    Neil Robertson and Paul D. Seymour. Graph minors. XX. Wagner’s conjecture.J. Comb. Theory B, 92(2):325–357, 2004. URL:https://doi.org/10.1016/j.jctb.2004.08.001, doi:10.1016/J.JCTB. 2004.08.001. 4, 5, 6

    work page doi:10.1016/j.jctb.2004.08.001 2004

  28. [28]

    Well-quasi-ordering infinite graphs with forbidden finite planar minor.Trans

    Robin Thomas. Well-quasi-ordering infinite graphs with forbidden finite planar minor.Trans. Amer. Math. Soc., 312(1):279–313, 1989.doi:10.2307/2001217. 6

    work page doi:10.2307/2001217 1989

  29. [29]

    An extremal function for contractions of graphs.Mathematical Proceedings of the Cambridge Philosophical Society, 95(2):261–265, 1984

    Andrew Thomason. An extremal function for contractions of graphs.Mathematical Proceedings of the Cambridge Philosophical Society, 95(2):261–265, 1984. 3

    1984

  30. [30]

    The extremal function for complete minors.Journal of Combinatorial Theory, Series B, 81(2):318–338, 2001.doi:10.1006/jctb.2000.2013

    Andrew Thomason. The extremal function for complete minors.Journal of Combinatorial Theory, Series B, 81(2):318–338, 2001.doi:10.1006/jctb.2000.2013. 3

    work page doi:10.1006/jctb.2000.2013 2001

  31. [31]

    Extremal functions for graph minors

    Andrew Thomason. Extremal functions for graph minors. In B. S. Webb, editor,Topics in Discrete Mathematics, volume 26 ofAlgorithms and Combinatorics, pages 359–380. Springer Berlin Heidelberg, Berlin, Heidelberg, 2006.doi:10.1007/978-3-540-32439-3_17. 3

    work page doi:10.1007/978-3-540-32439-3_17 2006

  32. [32]

    On the extremal function for graph minors.J

    Andrew Thomason and Matthew Wales. On the extremal function for graph minors.J. Graph Theory, 101(1):66–78, 2022. URL:https://doi.org/10.1002/jgt.22811,doi:10.1002/JGT.22811. 3

    work page doi:10.1002/jgt.22811 2022

  33. [33]

    A tight Erdős- Pósa function for planar minors.Adv

    Wouter Cames van Batenburg, Tony Huynh, Gwenaël Joret, and Jean-Florent Raymond. A tight Erdős- Pósa function for planar minors.Adv. Comb., pages Paper No. 2, 33, 2019.doi:10.19086/aic.10807. 7 31

    work page doi:10.19086/aic.10807 2019