The price of homogeneity is polynomial

2026/02/02 by Maximilian Gorsky, Michał T. Seweryn, Sebastian Wiederrecht · 1 voice · 2 citations
Computer Science · Mathematics · #cs.DM #math.CO

paper · pdf · doi:10.48550/arxiv.2602.01882

arxiv published 2026/02/02 · arxiv updated 2026/06/28

Abstract

We provide explicit and polynomial bounds for the Homogeneous Wall Lemma which occurred for the first time implicitly in the 13th entry of Robertson and Seymour's Graph Minors Series [JCTB 1990] and has since become a cornerstone in the algorithmic theory of graph minors. A wall where each brick is assigned a set of colours is said to be homogeneous if each brick is assigned the same set of colours. The Homogeneous Wall Lemma says that there exists a function h that, given non-negative integers q and k and an h(q,k)-wall W where each brick is assigned a, possibly empty, subset of \ 1, … , q \ contains a k-wall W' as a subgraph such that, if one assigns to each brick B of W' the union of the sets assigned to the bricks of W in its interior, then W' is homogeneous. It is well-known that h(q,k) ∈ k^O(q). The Homogeneous Wall Lemma plays a key role in most applications of the Irrelevant Vertex Technique where an exponential dependency of h on q usually causes non-uniform dependencies on meta-parameters at best and additional exponential blow-ups at worst. By proving that h(q,k) ∈ O(q⁴ ⋅ k⁶), we provide a positive answer to a problem raised by Sau, Stamoulis, and Thilikos [ICALP 2020].

Citations

• Colorful Minors
• Graph modification of bounded size to minor-closed classes as fast as vertex deletion
• Polynomial Bounds for the Graph Minor Structure Theorem
• Polynomial Bounds in the Apex Minor Theorem
• Parameterizing the quantification of CMSO: model checking on minor-closed graph classes
• Minor Containment and Disjoint Paths in almost-linear time
• Edge-Disjoint Paths in Eulerian Digraphs
• Fully dynamic approximation schemes on planar and apex-minor-free graphs
• Proof of the Clustered Hadwiger Conjecture
• Model Checking Disjoint-Paths Logic on Topological-Minor-Free Graph Classes
• Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes
• k-apices of minor-closed graph classes. I. Bounding the obstructions
• A more accurate view of the Flat Wall Theorem
• Quickly excluding a non-planar graph
• k-apices of minor-closed graph classes. II. Parameterized algorithms
• Hitting Topological Minors is FPT
• A lower bound on the tree-width of graphs with irrelevant vertices
• Towards Tight(er) Bounds for the Excluded Grid Theorem
• Improved Bounds for the Flat Wall Theorem
• List-coloring apex-minor-free graphs
• Explicit bounds for graph minors
• A New Proof of the Flat Wall Theorem
• Bidimensionality and Kernels
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• Graph Minors. XVI. Excluding a non-planar graph
• Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
• Local tree-width, excluded minors, and approximation algorithms
• Local Tree-Width, Excluded Minors, and Approximation Algorithms
• Graph minors. V. Excluding a planar graph
• Linearity of grid minors in treewidth with applications through bidimensionality

Cited by

• Adjacency labelling for proper minor-closed graph classes
• Quickly excluding an annotated planar graph

Discussions

• #New_arXiv_paper *Maximilian Gorsky*, Michał T. Seweryn, and Sebastian Wiederrecht, The price of homogeneity is polynomial, 2026. arxiv.org/abs/2602.01882 [bsky, 0 points, 0 comments]

Related

• A more accurate view of the Flat Wall Theorem
• Improved Bounds for the Flat Wall Theorem
• A New Proof of the Flat Wall Theorem
• A polynomial regularity lemma for semi-algebraic hypergraphs and its applications in geometry and property testing
• Smooth approximations and CSPs over finitely bounded homogeneous structures