A quasi-polynomial bound for the minimal excluded minors for a surface

Sarah Houdaigoui, Ken-ichi Kawarabayashi

Introduction

In the field of topological graph theory, a fundamental question involves determining whether a graph can be embedded into a specific surface—such as a sphere, a torus, or a Klein bottle—without any edges crossing. When a graph cannot be so embedded, it must contain a "forbidden" structure known as a minimal excluded minor. While it has been known for decades that the number of such forbidden graphs for any given surface is finite, the upper bound on their size has remained astronomically high.

In a significant breakthrough, Sarah Houdaigoui and Ken-ichi Kawarabayashi have provided the first quasi-polynomial bound for the size of these minimal excluded minors. This result effectively shatters a thirty-year-old double-exponential barrier, moving the theoretical understanding of graph minors from the realm of the unmanageable toward a more precise polynomial target.

Historical Context and the Problem

The study of excluded minors began with Kuratowski’s Theorem in 1930, which identified the two forbidden graphs for a plane (genus 0): $K_5$ and $K_{3,3}$. For surfaces of higher genus $g$, the problem becomes significantly more complex. In 1990, as part of the landmark Graph Minor Project, Robertson and Seymour proved that for any surface $S$, the set of minimal excluded minors is finite. However, their non-constructive proof did not provide a practical bound on the size of these graphs.

The first explicit upper bound was established by Paul Seymour in 1993. This bound was double-exponential in the genus ($2^{2^{poly(g)}}$), creating a massive disparity between the known lower bounds (which are linear) and the theoretical maximum. For thirty years, this double-exponential ceiling was the state of the art, leaving researchers with a gap that suggested either the graphs could be unimaginably large or the proof techniques were insufficiently sharp.

Methodological Breakthroughs

Houdaigoui and Kawarabayashi achieved their quasi-polynomial result by decomposing the structural constraints of a hypothetical minimal excluded minor $G$ into several manageable components.

1. The Nested Cycle Constraint

The primary catalyst for the new bound was a refinement of how many disjoint, nested, contractible cycles a minimal excluded minor can contain. Previous literature assumed this bound was $O(g)$. The authors proved that $G$ cannot contain more than $O(\log g)$ such cycles. This logarithmic refinement is the mathematical engine that drives the reduction from exponential to quasi-polynomial complexity.

2. Bounding Local Complexity

The authors established the first-ever bounds on the local complexity of these graphs. Specifically, they bounded the maximum degree of any vertex and the maximum size of a "face" (the regions bounded by edges in an embedding). By proving that these graphs cannot possess extremely high-degree vertices or massive faces without losing their status as "minimal" or becoming embeddable, the researchers significantly constrained the possible topology of the excluded minors.

3. Tree Decomposition and Pathwidth

The research introduces a new method to bound the "height" of the tree in a graph's tree decomposition. By limiting this height, the authors effectively limited the total number of vertices. Furthermore, they utilized a strategic "switch" to pathwidth—a linear variation of treewidth—to further refine the vertex count.

Key Results

The paper's primary contribution is the establishment of a new upper bound: the order (number of vertices) of a minimal excluded minor for a surface of Euler genus $g$ is at most $g^{O(\log^3 g)}$.

In addition to the main bound, the authors achieved several auxiliary results:

  • Treewidth Improvement: The bound on the treewidth of these graphs was improved from $O(g^3)$ to $O(g \log g)$, providing a much tighter structural "skeleton."
  • Grid Minors: The authors improved the bound on the size of a grid minor that must exist within these graphs, refining a 1997 result by Thomassen.
  • Lower Bound Analysis: The paper includes an appendix demonstrating a tight lower bound of approximately $L(g) \approx \sqrt{6g}$, confirming that while the new upper bound is a massive improvement, there remains a gap to be closed.

Conclusion and Future Directions

The transition from a double-exponential to a quasi-polynomial bound represents a landmark shift in graph minor theory. However, the authors note that the ultimate goal remains a purely polynomial bound.

Future research will likely focus on two specific bottlenecks identified in this work:

  1. Determining if the $O(\log g)$ bound for nested cycles can be further reduced.
  2. Investigating whether the maximum degree and face size can be bounded by a polynomial function of $g$ rather than the current quasi-polynomial $g^{O(\log^2 g)}$.

By addressing these constraints, the mathematical community may finally reach a polynomial bound, completing a journey in topological graph theory that began nearly a century ago.

Summary updated

BibTeX
@inproceedings{houdaigoui2026quasi,
  author = {Sarah Houdaigoui and Ken-ichi Kawarabayashi},
  title = {{A quasi-polynomial bound for the minimal excluded minors for a surface}},
  booktitle = {SODA},
  year = {2026},
  doi = {10.1137/1.9781611978971.167},
}
Figure