Pith. sign in

REVIEW 1 major objections 4 minor 2 references

The price of homogeneity is polynomial

T0 review · 1 major / 4 minor · reviewed 2026-08-03 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The Homogeneous Wall Lemma, long believed to require walls exponential in the number of colours, is proved with polynomial bounds O(q^4·k^6).

desk verdict Important new polynomial bound, but the final step of Theorem 1.1 has a genuine gap: colors witnessed in uniform C-bridges may escape the brick's restricted interior. read the letter →

arxiv 2602.01882 v3 pith:G6FYFSFH submitted 2026-02-02 math.CO cs.DM

Maximilian Gorsky , Micha{l} T. Seweryn , Sebastian Wiederrecht This is my paper · ORCID
classification math.COcs.DM MSC 05C8305C85
keywords homogeneouswalllemmaflattheoremgraphminorsirrelevantvertextechniquecolourfulgraphstanglesparameterizedalgorithmshomogenisation
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper proves that homogenising a coloured wall costs only polynomially, not exponentially. Given a flat wall whose bricks each carry a subset of q colours, it finds a smaller flat wall, as a subgraph of the original, in which every brick carries the same colour set; the required starting wall has size O(q^4·k^6). Previous arguments needed k^{O(q)}. Because the smaller wall keeps the same flatness certificate and its tangle is a truncation of the original, all known uses of the Homogeneous Wall Lemma in the Irrelevant Vertex Technique go through unchanged. The result answers an open question about whether the exponential 'price of homogeneity' was unavoidable.

What carries the argument

Meshes: an (n×m)-mesh is a grid-like union of n horizontal and m vertical pairwise internally disjoint paths crossing in order, and every wall is a mesh. The proof homogenises in stages: pack disjoint strips, pad each strip with buffer zones around a core, overlay row and column packings to form tiles, crop away end tiles, sort colours by abundance, build a mesh with a rainbow middle row, then weave vertical paths around that row to obtain a uniform mesh. The tangle-truncation requirement is certified by a path-packing observation: if a low-order separation split the new mesh, the original mesh would contain many disjoint paths between the two sides, contradicting the separation.

What would settle it

Take a q-colourful graph with a flat wall of order just above q^4·k^6 and test whether every flat homogeneous k-wall subgraph with truncating tangle has size super-polynomial in q and k. An explicit colouring where any homogeneous subgraph must span exponentially many bricks would refute the bound: for example, arrange colours so that each brick carries a unique subset pattern and no two distant bricks agree, forcing homogenisation to bridge many bricks.

Watch

Extended reading notes

Core claim

Theorem 1.1 states that there is a function f(q,k) in O(q^4·k^6) such that every q-colourful graph carrying a flat f(q,k)-wall W0 contains a flat homogeneous k-wall W1 as a subgraph of W0, with the tangle of W1 a truncation of the tangle of W0, and W1 computable in poly(q+k)||G|| time. A homogeneous wall here means the colours split into an inside set and an outside set: no outside colour appears in the compass, and each inside colour appears in a bridge inside every brick. The central move is to allow W1 to be a subgraph rather than a literal subwall: as long as the flatness witness is inherited and the tangle truncates, the object is as useful as a subwall for every known application. That

Load-bearing premise

The whole proof leans on one transfer: after cropping, trimming, and weaving, the new smaller wall is still flat, witnessed by the very same almost-embedding that witnessed the original wall; if that certificate can fail on subgraphs, the construction is not certified. A secondary assumption, not part of the main proof, is that a subgraph with a truncating tangle is as good as a subwall for every known application.

Editorial extensions

If this is right

  • Any algorithm that used the Homogeneous Wall Lemma now starts from a flat wall of size polynomial in q and k instead of k^{O(q)}.
  • Corollary 1.3: the k-H-Minor Deletion algorithm runs in time 2^{O(f(H)·k^16)}|G|^2, removing the previous non-uniform dependence where the polynomial degree depended on the fixed minor family.
  • The treewidth threshold in the Disjoint Paths algorithm improves from 2^{O(g(k))} to g(k)^{O(1)}, where g(k) is the unique linkage bound.
  • The homogeneous wall can be computed in poly(q+k)·||G|| time, so the improvement is algorithmic, not merely existential.
  • Within the graph-minor pipeline, homogeneity stops being a source of exponential or non-uniform blow-up; the unique linkage function remains the main non-polynomial pillar.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • An implication the authors leave implicit is that other uses of homogenisation, such as structuring apex vertices in almost-embeddings, may inherit polynomial bounds because the tangle-truncation condition is exactly what those arguments require.
  • A testable extension: the authors suggest the k-exponent can likely be improved by going directly from the tile lemma to a homogeneous mesh, skipping the rainbow-middle-row step; attempting that would yield a concrete smaller polynomial.
  • The same strip-and-tile strategy may homogenise richer colouring models, such as profiles attached to cliques of size three in reductions, with the same polynomial overhead.
  • If insisting on a literal subwall forces exponential dependence, then this subgraph-with-truncating-tangle formulation may be the strongest polynomial surrogate available.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 4 minor

Summary. The paper claims a polynomial bound for the Homogeneous Wall Lemma: for every q-colorful graph and every flat f(q,k)-wall W0 with f(q,k)=O(q^4 k^6), there exists a flat k-wall W1 contained in W0, witnessed flat by the same rendition, whose tangle is a truncation of the tangle of W0, and which is homogeneous. The proof proceeds through a sequence of quantitative lemmas: homogenization of strip packings, tiling arguments, construction of a mesh with a rainbow middle row, conversion to a uniform mesh, and finally a translation from uniform meshes to homogeneous walls. An explicit polynomial f(q,k) is given, and an algorithm running in time poly(q+k)||G|| is claimed.

Significance. If correct, the result resolves an open problem raised by Sau, Stamoulis, and Thilikos and removes the exponential 'price of homogeneity' from several parameterized algorithms based on the Irrelevant Vertex Technique. The paper gives an explicit polynomial bound, an algorithmic statement, and argues that the weakened output (a subgraph with the same tangle instead of a literal subwall) is sufficient for known applications. These are substantial contributions. The proof is not machine-checked and relies in places on geometric intuition, but the overall strategy is coherent and the quantitative claims are explicit.

major comments (1)
  1. [§5, proof of Theorem 1.1, final paragraph]
minor comments (4)
  1. [§5, proof of Theorem 1.1] There is a typo in the first lines: 'Let n := f(qk)' should presumably be 'Let n := f(q,k)'.
  2. [§4, Lemma 4.2 and §5, Lemma 5.1] The geometric constructions are described with reference to Figures 15–18 and phrases such as 'it is easy to observe' and 'clearly'. For a paper whose main claim is a quantitative theorem, the formal routing details in these two lemmas should be expanded; as written they are hard to verify independently of the figures.
  3. [§3, definition of interior of a brick] The definition of the interior of a brick B excludes B-bridges that contain a vertex of W−V(B). This is a strong condition and is not explicitly checked in the final paragraph of the proof of Theorem 1.1; it should be stated clearly how the constructed C-bridges satisfy it, especially if any of them meet B.
  4. [§1.2, Corollary 1.3] The claimed corollary depends on an analysis of [MSST23] that is only sketched. It would be helpful to state exactly which quantities in that proof are replaced by the polynomial f(q,k).

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the polynomial Homogeneous Wall Lemma is derived by an internal constructive chain; self-citations are contextual, not load-bearing.

full rationale

The proof of Theorem 1.1 is a constructive chain (Lemma 3.1 → Lemma 3.2 → Lemma 3.3 → Lemma 4.2 → Lemma 5.1 → Corollary 5.2 → Theorem 1.1) with no fitted parameters and no prediction-vs-fit structure. Quantities such as r, p, b, and q are chosen explicitly, and each lemma proves its output properties rather than assuming the target homogeneity. The paper's self-citations, mainly to the authors' companion work [GSW25] for rendition/flatness definitions and for context on the Graph Minor Structure Theorem, are not load-bearing: the definitions are restated in Section 2.3, and the lemmas establishing flatness inheritance and tangle truncation argue directly via Observation 4.1 and the structure of meshes. There is no imported 'uniqueness theorem' that forces the construction, and no ansatz is smuggled in by citation: the cosh-style rescaling mentioned in the instructions does not appear; the flatness witness framework is developed in the paper itself. The most delicate local inference is in the final paragraph of the proof of Theorem 1.1, where the authors assert that C-bridges carrying all colors must be contained in the B-bridge H. A skeptical reader may view this containment as insufficiently justified, since a C-bridge may intersect the brick B and continue outside the B-bridge. However, that is a potential correctness gap in a specific topological argument, not a reduction of the theorem to its own inputs, and therefore it is not circularity under the required standard. The paper's own Section 6 caveats—that the bounds are likely not optimal and that homogenizing transactions would require additional arguments—are limitations, not circular steps. Overall, the main theorem is self-contained with respect to the non-standard notions it introduces, and no circularity score is warranted.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The theorem is not fitted: every constant in f(q,k) is derived from explicit recurrences in the lemmas. The proof relies on standard graph-minor background (tangles, walls/meshes, flatness witnesses) rather than on the result being proved. No new particles, forces, or empirically fitted parameters appear.

assumptions (5)
  • standard math Every n-wall is an n-mesh and every 2n-mesh contains an n-wall; meshes capture the same structure as walls.
    Section 2.2 states this without proof; it lets the proof work with meshes and then convert the final mesh back into a wall in Theorem 1.1.
  • standard math The orientation T_M defined by an (r×ℓ)-mesh is a tangle of order ℓ.
    Section 2.2 cites [RS91]; this is used in the tangle-truncation arguments in Lemma 4.2 and Corollary 5.2.
  • domain assumption A flat wall has a sphere-rendition witness with a single vortex, and this witness, with its interiors and compasses, is inherited by suitable subgraphs.
    Section 3 defines flatness this way; Lemmas 4.2 and 5.1 assert that the constructed meshes remain flat witnessed by the same ρ after cropping and weaving.
  • standard math Observation 4.1: if a vertex set meets at least k distinct horizontal or vertical paths of an (n×m)-mesh, there are k disjoint paths from any horizontal or vertical path to that set.
    Used at the end of Lemma 4.2 to show that the tangle of the new mesh is a truncation of the tangle of the original mesh.
  • domain assumption Planar geometry of strips: a strip's frame and padding support the path-extension and weaving constructions in Lemmas 4.2 and 5.1.
    The proof relies on routing paths through buffer zones without leaving the compass of the relevant mesh, which is a consequence of the rendition-theoretic planar-like structure of flat walls.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The price of homogeneity is polynomial." pith.science (2026). https://pith.science/paper/G6FYFSFH

@misc{pith2026260201882,
  author       = {Pith},
  title        = {Pith review of: The price of homogeneity is polynomial},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/G6FYFSFH}},
  note         = {Machine review of arXiv:2602.01882}
}
abstract

We provide explicit and polynomial bounds for the Homogeneous Wall Lemma which occurred for the first time implicitly in the $13$th 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, \ldots , 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) \in k^{\mathcal{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) \in \mathcal{O}(q^4 \cdot k^6)$, we provide a positive answer to a problem raised by Sau, Stamoulis, and Thilikos [ICALP 2020].

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

2 extracted references

  1. [275]

    9781611973730.20

    Society for Industrial and Applied Mathematics, October 2015.doi:10.1137/1. 9781611973730.20. [CKK24] Dario G Cavallaro, Ken-ichi Kawarabayashi, and Stephan Kreutzer. Edge-Disjoint Paths in Eulerian Digraphs. InProceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 704–715, Vancouver BC Canada, June 2024. ACM. doi:10.1145/3618260.36497...

    arXiv 2015

  2. [2024]

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

    IEEE.doi:10.1109/FOCS61266.2024.00014. [KTW18] Ken-ichi Kawarabayashi, Robin Thomas, and Paul Wollan. A new proof of the flat wall theorem.Journal of Combinatorial Theory, Series B, 129:204–238, March 2018. doi:10.1016/j.jctb.2017.09.006. [KTW21] Ken-ichi Kawarabayashi, Robin Thomas, and Paul Wollan. Quickly excluding a non- planar graph, January 2021.arX...

    arXiv 2024

Pith tools

Reviewed August 3, 2026 · model on record in the stance chip above.