The price of homogeneity is polynomial

Maximilian Gorsky ​ Discrete Mathematics Group, Institute for Basic Science (IBS), South Korea Michał T. Seweryn Sebastian Wiederrecht School of Computing, KAIST, South Korea · 2026

Read The price of homogeneity is polynomial by Maximilian Gorsky ​ Discrete Mathematics Group, Institute for Basic Science (IBS), South Korea Michał T. Seweryn Sebastian Wiederrecht School of Computing, KAIST, South Korea (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-01882.txt.

Description

Maximilian Gorsky and colleagues give explicit polynomial bounds for the Homogeneous Wall Lemma. The lemma first appeared in Robertson and Seymour's 13th Graph Minors entry. A wall with bricks is homogeneous when every brick carries the same color set. The lemma says a wall with bricks colored from q colors contains a k wall. The bound grew like k to a power growing with q, causing non uniform dependencies and blow ups. Their new bound grows like q to the fourth times k to the sixth, answering Sau and coauthors.

Catalog record

CREATORMaximilian Gorsky ​ Discrete Mathematics Group, Institute for Basic Science (IBS), South Korea Michał T. Seweryn Sebastian Wiederrecht School of Computing, KAIST, South Korea
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE146360
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602.01882

Browse the full library · About the Tower of Babel