{"id":"c12a6614-83f8-4d28-aa92-2a260f168e65","arxiv_id":"2602.01882","paper_version":3,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The Homogeneous Wall Lemma holds with h(q,k) = O(q^4 k^6), replacing the previous exponential-in-q bounds.","lead":"New proof gives polynomial bounds for a core lemma in graph minors, replacing an exponential dependence on the number of colors. This removes a known runtime bottleneck in many parameterized algorithms built on the Irrelevant Vertex Technique.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Final homogenization step in proof of Theorem 1.1 is unsupported: a C-bridge may cross the brick boundary B, so colors in int(C) need not lie in the B-bridge H.","rationale":"The reader identified the inheritance of the flatness witness as the weakest assumption. That concern is real but largely definitional: the paper's framework from [KTW18, GSW25] is designed so that subgraphs of a flat mesh inherit the witness, and the authors rely on that. The more load-bearing issue is the final step from uniformity to homogeneity, which is not just a matter of witness inheritance but a missing logical link. The proof claims that colors in the interior of the central cycle C are automatically contained in the B-bridge H, but C-bridges can cross the boundary B. Since the definition of the interior of a brick in the homogeneity definition is restrictive (B-bridges must avoid W1−V(B) and not be bridges of other bricks), the transfer from uniformity is not automatic. The paper's own notation conflates two different objects: the B-bridge H and the set of C-bridges supplied by uniformity. The assertion that the latter are contained in the former is unsupported and, in the described configuration, can be false. This gap affects exactly the theorem's central claim: that the output wall is homogeneous. It may be patchable by a more careful argument, but as written the proof is incomplete. Therefore the verdict should be CONDITIONAL rather than ACCEPT: the main theorem should be accepted only after a rigorous proof that uniformity of the intermediate mesh implies homogeneity of the selected coarse wall.","tokens_in":38675,"tokens_out":19773,"duration_ms":188358,"concrete_test":"Re-derive the final paragraph of Theorem 1.1 with a path-by-path argument, and test the minimal case: take W to be a 6×6 wall (or the corresponding 3-wall), choose W1 using rows/columns 1 and 4, and place a single color on an intermediate horizontal path strictly between P4 and P5 but inside the perimeter of W. Verify that W satisfies the uniformity condition for every cycle. Then determine whether the color is contained in some B-bridge of the brick B that avoids W1−V(B). If no such bridge exists, the final homogenization step fails on this example.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The proof of Theorem 1.1 ends by converting a uniform mesh W into a homogeneous wall W1. In the last paragraph, for a brick B of W1, the authors choose the cycle C in the middle of B and assert that C lies in a B-bridge H. They then use uniformity of W to find C-bridges carrying all colors of χ(V(W1)) and conclude that these C-bridges are contained in H, so H carries all colors. The containment step is not justified. A C-bridge is allowed to intersect B: since B is a cycle of W1⊆W, a path from C to outside the macro-cell can cross B at a vertex of B and continue beyond it. Such a bridge is still a C-bridge contained in compass(W), so uniformity of W places its colors in int(C). But after deleting V(B), the part of the bridge outside B lies in a different component and is not part of the B-bridge H. The sentence 'the bridges in H must be disjoint from W−V(C)' does not follow from containment in the interior of the perimeter of W, and even if it did, disjointness from W−V(C) would not imply inclusion in H. Thus the paper does not actually prove that every color in I is witnessed by a B-bridge in the restricted interior of B. This is a concrete gap in the derivation of the central claim, not merely a picture-driven omission.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":39008,"tokens_out":12757,"duration_ms":130527,"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":[{"comment":"","section":"§5, proof of Theorem 1.1, final paragraph"}],"minor_comments":[{"comment":"There is a typo in the first lines: 'Let n := f(qk)' should presumably be 'Let n := f(q,k)'.","section":"§5, proof of Theorem 1.1"},{"comment":"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.","section":"§4, Lemma 4.2 and §5, Lemma 5.1"},{"comment":"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.","section":"§3, definition of interior of a brick"},{"comment":"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).","section":"§1.2, Corollary 1.3"}],"recommendation":"major_revision","confidential_remarks":"The first reader's report is more optimistic than I am. The gap I identify is in the very last step of the proof of Theorem 1.1 and is not a matter of presentation: the assertion that C-bridges witnessing uniformity lie inside the B-bridge H is unsupported and in fact false under the paper's own definitions. The main structural lemmas may well be salvageable, but the homogenization step needs a substantive fix. I recommend sending the paper back for major revision rather than accepting it in its current form."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The polynomial bound itself is the real news, and the machinery around strips, padded packings, tiles, and the rainbow-middle-row construction is a genuine advance. Replacing the subwall requirement with a subgraph that shares the tangle and flatness witness looks like the right move, and the explicit f(q,k) with the algorithmic version makes this directly usable. Credit where it's due: this answers the Sau–Stamoulis–Thilikos question and removes an exponential bottleneck that actually mattered in applications.\n\nThe soft spot is not cosmetic. The last paragraph of the proof of Theorem 1.1 argues that, for a brick B and the inner cycle C, the C-bridges supplied by uniformity lie inside the B-bridge H and therefore all colors appear in the restricted interior of B. That containment is not justified. A C-bridge contained in compass(W) may touch a vertex of B and continue outside B; it is still a C-bridge, so uniformity places its colors in int(C), but it is not a B-bridge of the kind allowed in the interior of B. The sentence \"the bridges in H must be disjoint from W−V(C)\" does not follow from containment in the interior of the perimeter, because the interior of the perimeter contains all of W except the perimeter itself. Even disjointness from W−V(C) would not automatically imply inclusion in the specific B-bridge H. The stress-test note is right: the final homogenization step is unsupported.\n\nThis is load-bearing, not a minor gap. The strip and tile lemmas may well be correct, and the uniform-mesh construction (Corollary 5.2) may stand, but the translation from uniform mesh to homogeneous wall is exactly what Theorem 1.1 promises, and that step is unproven as written. The reader's report missed this; I think the stress-test has it right.\n\nI would still send this to peer review. The result is important and the rest of the paper is substantial and seriously argued. But I would flag the final paragraph explicitly and expect the authors to supply a fix—perhaps by choosing C more carefully, using the spacing between the paths in W1, or proving that the relevant C-bridges can be rerouted to avoid B. Without that, the main theorem does not currently go through.\n\nFor the reading group: worth reading to discuss the construction and the gap, but not something to cite as a proved theorem yet.","headline":"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.","tokens_in":39485,"tokens_out":5771,"would_cite":false,"duration_ms":51800,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C83","05C85"],"pacs":[],"model":"deepseek-v4-flash","headline":"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).","keywords":["homogeneous wall lemma","flat wall theorem","graph minors","irrelevant vertex technique","colourful graphs","tangles","parameterized algorithms","wall homogenisation"],"falsifier":"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.","tokens_in":38584,"feed_emoji":"🧱","tokens_out":4467,"duration_ms":47009,"temperature":0.7,"pith_summary":"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.","feed_headline":"Homogeneous walls now cost O(q^4 k^6), not k^{O(q)}","feed_subtitle":"Graph-minor algorithms that needed exponentially large walls for homogenisation now start from a polynomial-sized wall.","key_machinery":"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.","core_discovery":"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","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["Homogeneous Wall Lemma: now proven in O(q^4 k^6)","Graph minors: homogeneity costs polynomial, not exponential","Polynomial solution to 2020 problem on homogeneous walls","Homogeneous walls: exponential to polynomial in one bound","From k^O(q) to q^4 k^6: the price of homogeneity is polynomial"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Homogeneous Wall Lemma: now proven in O(q^4 k^6)","Graph minors: homogeneity costs polynomial, not exponential","Polynomial solution to 2020 problem on homogeneous walls","Homogeneous walls: exponential to polynomial in one bound","From k^O(q) to q^4 k^6: the price of homogeneity is polynomial"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000213,"raw_usage":{"total_tokens":1315,"prompt_tokens":857,"completion_tokens":458,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":601,"completion_tokens_details":{"reasoning_tokens":367}},"tokens_in":601,"tokens_out":458,"duration_ms":4700,"temperature":1.0,"reasoning_tokens":367,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T05:30:57.146068+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}