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
| CREATOR | Maximilian Gorsky Discrete Mathematics Group, Institute for Basic Science (IBS), South Korea Michał T. Seweryn Sebastian Wiederrecht School of Computing, KAIST, South Korea |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 146360 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602.01882