arxiv: 2604.02796 · v1 · submitted 2026-04-03 · 🧮 math.CO · cs.DM

Recognition: 2 theorem links

· Lean Theorem

A polynomial bound for the minimal excluded minors for a surface

Sarah Houdaigoui , Ken-ichi Kawarabayashi

Authors on Pith no claims yet

Pith reviewed 2026-05-13 19:13 UTC · model grok-4.3

classification 🧮 math.CO cs.DM

keywords graph minorsexcluded minorssurface embeddingsEuler genusnested cyclesseparatorspolynomial bounds

0 comments

The pith

Minimal excluded minors for a surface of genus g have order O(g^{8+ε}) for every ε>0.

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

This paper establishes a polynomial upper bound on the size of minimal excluded minors for graphs embeddable on a surface of genus g. Earlier work gave a quasi-polynomial bound, leaving a large gap to the known linear lower bound of order g. The proof proceeds by replacing a genus-dependent structural theorem with a separator-dependent one: any contractible subgraph whose boundary separator has size s contains only O(log s) nested contractible cycles. Once this local bound is in hand, standard counting arguments produce the global polynomial bound on the whole minor. A reader would care because the result makes the finite list of forbidden minors for each surface far more explicit in its growth rate and narrows the remaining gap to the conjectured linear optimum.

Core claim

Let G be a minimal excluded minor for a surface of Euler genus g. Then the order of G is O(g^{8+ε}) for every ε>0. The argument rests on a new separator-based strengthening: for any contractible subgraph H of G whose separator has size s, some embedding of G contains O(log s) pairwise disjoint contractible nested cycles inside H. This separator-dependent count replaces earlier genus-dependent counts and yields the polynomial bound after standard reductions from the graph-minors machinery.

What carries the argument

Separator-based strengthening of nested contractible cycles: any contractible subgraph with a separator of size s contains O(log s) pairwise disjoint contractible nested cycles in some embedding of G.

If this is right

The number of vertices in any minimal excluded minor for genus g grows at most polynomially in g.
Recognition algorithms for surface embeddability inherit polynomial dependence on g from the size of the forbidden list.
The asymptotic gap between upper and lower bounds on excluded-minor size shrinks from quasi-polynomial to polynomial.
Any future improvement must focus on lowering the exponent 8 or removing the ε term.

Where Pith is reading between the lines

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

The same separator-reduction technique may apply to other minor-closed families whose structural theorems currently depend on global parameters such as tree-width or genus.
For small fixed g one could computationally enumerate excluded minors and test whether their sizes already obey the O(g^8) envelope.
If the log s factor can be replaced by a constant, the exponent would drop further.

Load-bearing premise

The separator-based strengthening holds: every contractible subgraph with a separator of size s contains only O(log s) nested contractible cycles.

What would settle it

A concrete minimal excluded minor for some genus g whose number of vertices exceeds C·g^{8+ε} for a fixed constant C and sufficiently large g would falsify the claimed bound.

Figures

Figures reproduced from arXiv: 2604.02796 by Ken-ichi Kawarabayashi, Sarah Houdaigoui.

**Figure 2.** Figure 2: shows an example of cycles on a spanning tree. a [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗

**Figure 3.** Figure 3: The subgraph Int(C, Π) of G is shown embedded in Π. The cycles C and Ce are represented in blue and green, respectively, and the edge e is represented in red. The bridges of B − BC are highlighted in pale blue, while the bridge BC consists of the remaining part of G − (Ce ∪ e). Definition 4.4 (Same relative orientation). Let H be a graph that is ΠH-embedded in a surface SH and Π′ H-embedded in a surface S… view at source ↗

**Figure 4.** Figure 4: Two cycles that have the same relative orientation. The cycles [PITH_FULL_IMAGE:figures/full_fig_p012_4.png] view at source ↗

**Figure 5.** Figure 5: The subgraph B is 2-separated from the rest of the graph by {a, b} and is contained in a disk in Π. The following result is a refinement of a result from [HK26, Theorem 4.16]. By adding basic constraints on the bounding function N, we can extend the bound N(g) on the order of the 2- connected excluded minors for a surface to a bound for all its excluded minors with the same function N(g). This improves the… view at source ↗

**Figure 6.** Figure 6: Contractible squares. The solid lines indicate paths, whereas the dotted line shows the [PITH_FULL_IMAGE:figures/full_fig_p016_6.png] view at source ↗

**Figure 7.** Figure 7: Illustration for the proof of Theorem 5.1. [PITH_FULL_IMAGE:figures/full_fig_p020_7.png] view at source ↗

**Figure 8.** Figure 8: Illustration for the end of the proof of Theorem 5.3. The vertices in [PITH_FULL_IMAGE:figures/full_fig_p022_8.png] view at source ↗

**Figure 9.** Figure 9: Illustration for the edge-sharing components and units in Theorem 5.4. The subgraphs [PITH_FULL_IMAGE:figures/full_fig_p023_9.png] view at source ↗

**Figure 10.** Figure 10: Illustration for the sets (Fi)i∈N∗ in Claim 5.5.1. The subgraphs in white correspond to faces that are not in B(C) because they don’t touch C. The sets S j≥1 F2j and S j≥0 F2j+1 are depicted respectively in blue and green. Remark that, in this example, for i > 5, Fi is empty. Remark that by construction, for j ≥ 1, Fj and Fj+2 contain vertex-disjoint faces. Moreover, remark that, for j ≥ 1, the faces in F… view at source ↗

**Figure 11.** Figure 11: Homotopic square. The zone represented in blue is [PITH_FULL_IMAGE:figures/full_fig_p027_11.png] view at source ↗

**Figure 12.** Figure 12: Fans from a vertex and a face. The solid lines indicate paths, whereas the dotted line [PITH_FULL_IMAGE:figures/full_fig_p034_12.png] view at source ↗

**Figure 13.** Figure 13: Fans with an arch from a vertex and a face. The solid lines indicate paths, whereas the [PITH_FULL_IMAGE:figures/full_fig_p035_13.png] view at source ↗

**Figure 14.** Figure 14: The set F(H) for a fan, and F(H) and Farch(H) for a fan with an arch. Let H be a fan (with or without an arch) from p with the horizontal path P. We can suppose that the signature on the edges of H in Π is positive, because H is Π-contractible. Let CH be the cycle of H so that H ⊆ Int(CH, Π). Then, a face f ∈ F(H) is an arched face if f does not intersect CH in a single segment (vertex or path). Let f ∈ F… view at source ↗

**Figure 15.** Figure 15: Illustration for arched faces and arches. The fan [PITH_FULL_IMAGE:figures/full_fig_p036_15.png] view at source ↗

**Figure 16.** Figure 16: Illustration for maximal arches. The edges inside a maximal arch are represented in [PITH_FULL_IMAGE:figures/full_fig_p037_16.png] view at source ↗

**Figure 17.** Figure 17: Radius of a contractible graph. The three colors indicate the radius of the faces with [PITH_FULL_IMAGE:figures/full_fig_p042_17.png] view at source ↗

read the original abstract

As part of the graph minor project, Robertson and Seymour showed in 1990 that the class of graphs that can be embedded in a given surface can be characterized by a finite set of minimal excluded minors. However, their proof, because existential, provides no explicit information about these excluded minors. In 1993, Seymour established the first upper bound on the order of such minimal excluded minors. Very recently, Houdaigoui and Kawarabayashi improved this result by deriving a quasi-polynomial upper bound. Despite this progress, the gap between this bound and the known linear lower bound $\Omega(g)$ (where $g$ denotes the genus) remains substantial. In particular, they conjectured that a polynomial upper bound should hold. In this paper, we confirm this conjecture by showing that the order of the minimal excluded minors for a surface of genus $g$ is $O(g^{8+\varepsilon})$ for every $\varepsilon >0$. This result significantly narrows the gap between the known lower and upper bounds, bringing the asymptotic behavior much closer to the conjectured optimum. Our approach introduces a new forbidden structure of minimal excluded minors. Let $G$ be a minimal excluded minor for a surface of Euler genus $g$. Houdaigoui and Kawarabayashi showed that $G$ contains $O(\log g)$ pairwise disjoint cycles that are contractible and nested in some embedding of $G$. We strengthen this result by proving a separator-based variant: for any contractible subgraph $H \subseteq G$ with a separator of size $s$ (with $H$ completely contained in one side), the subgraph $H$ contains $O(\log s)$ disjoint cycles that are contractible and nested in some embedding of $G$. This allows us to replace a genus-dependent bound with a separator-dependent one, which is the main new ingredient in deriving our polynomial bound.

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.

Desk Editor's Note private letter to a colleague

This paper gives the first polynomial upper bound O(g^{8+ε}) on minimal excluded minors for genus-g surfaces by replacing a genus-dependent cycle count with a separator-dependent one.

read the letter

This paper gives the first polynomial upper bound on the size of minimal excluded minors for a surface of genus g. The bound is O(g^{8+ε}) for any ε > 0. They achieve this by strengthening their earlier result on nested cycles. Instead of O(log g) cycles that depend on the genus, they prove that any contractible subgraph H with a separator of size s contains O(log s) such cycles. This local dependence lets them run a recursion controlled by separator sizes, which stays polynomial after the ε slack is added in. The paper does well at laying out this strategy and connecting it to the Robertson-Seymour theorem and Seymour's 1993 bound. The improvement over their own recent quasi-polynomial result is clear and substantive. The soft spot is in the details of the new separator lemma. It needs to be checked that the O(log s) bound carries no hidden genus factors and that the recursion does not reintroduce super-polynomial terms when the separators themselves are contractible subgraphs of the minor. The stress-test note flags exactly this point, so the full proof will have to confirm the strengthening holds cleanly. This is for structural graph theorists who want explicit bounds on minor-closed classes and their algorithmic consequences. A reader interested in surface embedding recognition or the structure of excluded minors will get value from it. It deserves a serious referee to verify the central lemma. I recommend sending it to peer review.

Referee Report

2 major / 2 minor

Summary. The paper proves that the minimal excluded minors for a surface of Euler genus g have order O(g^{8+ε}) for every ε>0. It strengthens the O(log g) nested contractible cycles result of Houdaigoui and Kawarabayashi to a separator-based version: any contractible subgraph H with a separator of size s contains O(log s) pairwise disjoint contractible nested cycles in some embedding of G. This replacement of the global genus parameter by the local separator size s is used to set up a recursion on the size of the minimal excluded minor whose solution yields the stated polynomial bound.

Significance. If the central lemma holds, the result is a substantial advance in the graph-minors project: it supplies the first polynomial upper bound on the order of minimal excluded minors for surfaces, confirming the conjecture of Houdaigoui and Kawarabayashi and reducing the gap to the known Ω(g) lower bound from quasi-polynomial to polynomial. The separator-based strengthening is a new combinatorial tool that may be reusable in other embedding and minor problems.

major comments (2)

[proof of the separator lemma] The separator-based strengthening (abstract and the proof of the new lemma): the O(log s) bound on the number of nested contractible cycles must be shown to have a constant independent of the global genus g. Any hidden g-dependence would re-introduce super-polynomial factors when the recursion is solved over a sequence of separators whose sizes are themselves bounded only in terms of g.
[main bound derivation] The size-recursion argument (the derivation of the O(g^{8+ε}) bound): when the lemma is applied to a contractible subgraph H whose own separator is a subgraph of the minimal excluded minor, the branching factor and depth of the recursion tree must be shown to remain polynomial after accounting for the ε. The current sketch does not explicitly bound the number of recursive calls generated by each separator.

minor comments (2)

[abstract] The abstract alternates between 'genus g' and 'Euler genus g'; a single consistent terminology should be used throughout, with a brief reminder of the relation between the two notions.
[statement of the new lemma] Notation for the embedding in which the cycles are nested should be introduced once and used uniformly; the current description leaves open whether the embedding is fixed or chosen depending on H.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and valuable comments on our manuscript. The points raised about constant independence in the separator lemma and explicit recursion bounds are well-taken, and we will revise the paper to address them directly.

read point-by-point responses

Referee: [proof of the separator lemma] The separator-based strengthening (abstract and the proof of the new lemma): the O(log s) bound on the number of nested contractible cycles must be shown to have a constant independent of the global genus g. Any hidden g-dependence would re-introduce super-polynomial factors when the recursion is solved over a sequence of separators whose sizes are themselves bounded only in terms of g.

Authors: The proof of the separator lemma establishes the O(log s) bound using only local properties of the contractible subgraph H and its separator of size s; the argument proceeds by iteratively finding contractible cycles via the separator and does not invoke the global genus g at any step. The constant in the O(log s) is therefore absolute. We will revise the manuscript to add an explicit statement of this independence together with a short paragraph outlining the proof structure that confirms the absence of g-dependence. revision: yes
Referee: [main bound derivation] The size-recursion argument (the derivation of the O(g^{8+ε}) bound): when the lemma is applied to a contractible subgraph H whose own separator is a subgraph of the minimal excluded minor, the branching factor and depth of the recursion tree must be shown to remain polynomial after accounting for the ε. The current sketch does not explicitly bound the number of recursive calls generated by each separator.

Authors: We agree the recursion sketch needs to be expanded. In the revision we will supply a complete analysis: each application of the lemma on a separator of size s produces at most O(log s) recursive subproblems, and the separator size decreases by a constant factor at each level (by removal of a cycle or reduction of the separator). Consequently the recursion depth is O(log g). The resulting total size is bounded by a polynomial whose degree is controlled by the choice of ε, which absorbs the logarithmic factors. We will insert this explicit bounding of branching factor and depth into the main bound derivation section. revision: yes

Circularity Check

0 steps flagged

Minor self-citation to prior quasi-polynomial result; new separator strengthening is independent

full rationale

The derivation introduces a new separator-based lemma (O(log s) nested contractible cycles for any contractible H with separator s) as the key ingredient to replace the prior O(log g) bound and obtain the O(g^{8+ε}) recursion. The cited O(log g) result from the same authors is used only for context and is not load-bearing for the polynomial improvement. No self-definitional equations, fitted parameters renamed as predictions, or reductions of the central claim to prior self-citations appear. The argument is self-contained against the stated combinatorial strengthening.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on the Robertson-Seymour finite excluded-minor theorem and a new separator-based structural lemma; no free parameters or invented entities are introduced.

axioms (1)

standard math Robertson-Seymour theorem that every surface has finitely many minimal excluded minors
Invoked as the existence result whose quantitative bound is improved.

pith-pipeline@v0.9.0 · 5650 in / 1122 out tokens · 46078 ms · 2026-05-13T19:13:01.494906+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We strengthen this result by proving a separator-based variant: for any contractible subgraph H ⊆ G with a separator of size s … the subgraph H contains O(log s) disjoint cycles that are contractible and nested

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

10 extracted references · 10 canonical work pages

[1]

Computing excluded minors

[AGK08] Isolde Adler, Martin Grohe, and Stephan Kreutzer. Computing excluded minors. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, pages 641– 650, 2008.doi:10.5555/1347082.1347153. [Arc80] Dan Archdeacon.A Kuratowski theorem for the projective plane. PhD thesis, The Ohio State University,

work page doi:10.5555/1347082.1347153 2008
[2]

A Kuratowski theorem for the projective plane.Journal of Graph Theory, 5(3):243–246, 1981.doi:10.1002/jgt.3190050305

[Arc81] Dan Archdeacon. A Kuratowski theorem for the projective plane.Journal of Graph Theory, 5(3):243–246, 1981.doi:10.1002/jgt.3190050305. [BW86] Rainer Bodendiek and Klaus Wagner. A characterization of the minimal basis of the torus.Combinatorica, 6(3):245–260,

work page doi:10.1002/jgt.3190050305 1981
[3]

53 [CT21] Julia Chuzhoy and Zihan Tan

URL:https://doi.org/10.1145/2820609. 53 [CT21] Julia Chuzhoy and Zihan Tan. Towards tight(er) bounds for the excluded grid theorem. Journal of Combinatorial Theory, Series B, 146:219–265, 2021.doi:10.1016/j.jctb. 2020.09.010. [Dec78] Richard Decker.The genus of certain graphs. PhD thesis, The Ohio State University,

work page doi:10.1145/2820609 2021
[4]

The genus of subgraphs ofK 8.Israel Journal of Mathematics, 11:452–455, 1972.doi:10.1007/BF02761469

[DH72] Richard Duke and Gary Haggard. The genus of subgraphs ofK 8.Israel Journal of Mathematics, 11:452–455, 1972.doi:10.1007/BF02761469. [FL89] Michael Fellows and Michael Langston. An analogue of the Myhill-Nerode theorem and its use in computing finite-basis characterizations.Annual Symposium on Foundations of Computer Science (Proceedings), pages 520...

work page doi:10.1007/bf02761469 1972
[5]

[GKR13] Martin Grohe, Ken-ichi Kawarabayashi, and Bruce Reed

doi:10.1016/0095-8956(79)90022-4. [GKR13] Martin Grohe, Ken-ichi Kawarabayashi, and Bruce Reed. A simple algorithm for the graph minor decomposition – logic meets structural graph theory —. InPro- ceedings of the 2013 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 414–431. Society for Industrial and Applied Mathematics, 2013.doi:10.1137/ 1...

work page doi:10.1016/0095-8956(79)90022-4 2013
[6]

The vertex separation number of a graph equals its path-width

[Kin92] Nancy Kinnersley. The vertex separation number of a graph equals its path-width. Information Processing Letters, 42(6):345–350, 1992.doi:10.1016/0020-0190(92) 90234-M. [KKR12] Ken-ichi Kawarabayashi, Yusuke Kobayashi, and Bruce Reed. The disjoint paths prob- lem in quadratic time.Journal of Combinatorial Theory, Series B, 102(2):424–435, 2012.doi:...

work page doi:10.1016/0020-0190(92 1992
[7]

[KTW20] Ken-ichi Kawarabayashi, Robin Thomas, and Paul Wollan

doi:10.4171/JEMS/1133. [KTW20] Ken-ichi Kawarabayashi, Robin Thomas, and Paul Wollan. Quickly excluding a non- planar graph.to appear in Memoirs of the American Mathematical Society. Soc.,

work page doi:10.4171/jems/1133
[8]

[Kur30] Kazimierz Kuratowski

doi:10.48550/arXiv.2010.12397. [Kur30] Kazimierz Kuratowski. Sur le probl` eme des courbes gauches en topologie.Fundamenta Mathematicae, 15(1):271–283,

work page doi:10.48550/arxiv.2010.12397 2010
[9]

London Mathe- matical Society Lecture Note Series

[Moh01] Bojan Mohar.Graph minors and graphs on surfaces, page 145–164. London Mathe- matical Society Lecture Note Series. Cambridge University Press, 2001.doi:10.1017/ CBO9780511721328.008. [MT01] Bojan Mohar and Carsten Thomassen.Graphs on surfaces. Baltimore, MD: Johns Hopkins University Press, 2001.doi:10.56021/9780801866890. [RS86a] Neil Robertson and...

work page doi:10.56021/9780801866890 2001
[10]

[Tho97] Carsten Thomassen

URL:https://web.math.princeton.edu/ ~pds/papers/surfacebound/bound.pdf. [Tho97] Carsten Thomassen. A simpler proof of the excluded minor theorem for higher surfaces. Journal of Combinatorial Theory, Series B, 70(2):306–311, 1997.doi:10.1006/jctb. 1997.1761. [TUK94] Atsushi Takahashi, Shuichi Ueno, and Yoji Kajitani. Minimal acyclic forbidden minors for th...

work page doi:10.1006/jctb 1997