{"id":"e1628fc3-9379-4d30-a270-8ce6772502a4","arxiv_id":"2507.06169","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"A simple construction gives layered-wheel-like graphs with arbitrarily large treewidth, arbitrarily large girth, and every outerstring induced subgraph of bounded treewidth, refuting Trotignon's conjecture.","lead":"A new family of layered-wheel-like graphs is constructed with arbitrarily large treewidth, girth, and separation of high-degree vertices. The construction refutes a conjecture of Trotignon while remaining much simpler than earlier examples.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Corollary 4.5's seven-path bound is the load-bearing step; the compressed proofs of Lemmas 4.3–4.4 leave a possible missed configuration that would break the K_{r0,r0}-minor-free claim.","rationale":"The central claim (Theorem 1.3) requires three exclusions: no large wall induced minor, no large complete bipartite induced minor, and bounded treewidth for outerstring induced subgraphs. The second exclusion rests entirely on Lemma 4.1, which via Lemma 4.2 reduces to showing no wide theta of width 8; that is exactly Corollary 4.5's at-most-seven internally anticomplete paths between any two vertices. Corollary 4.5 is therefore a single point of failure: if a missed configuration allows eight such paths, Lemma 4.1 fails and property (ii) of Theorem 1.3 is unproved. The reader's verdict identifies the same step. I agree with that identification; the proofs of Lemmas 4.3 and 4.4 are terse, and the specific assertions about layers require more justification. I have not found a concrete counterexample, and the authors' remark that the true bound is at most three suggests the claim is very likely correct. Therefore the correct response is to keep the reader's CONDITIONAL verdict pending an independent check rather than to reject. The proposed computational check for small parameters can falsify Corollary 4.5 if it is wrong, and otherwise provides supporting evidence. This is not an ad hominem or consensus-based objection; it is a request to verify the most intricate combinatorial step.","tokens_in":17091,"tokens_out":33029,"duration_ms":324084,"concrete_test":"For g=1 and k=4,5,6, compute for every pair of vertices of G^1_k the maximum size of a set of pairwise internally anticomplete paths, using an exact backtracking search or a small MILP. If any pair admits at least 8 such paths, Corollary 4.5 is false and the main theorem collapses; if all tested pairs admit at most 7, the load-bearing concern is mitigated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing step is Corollary 4.5, which bounds the number of pairwise internally anticomplete paths between any two vertices by seven. The proof splits paths into standard/nonstandard and bounds nonstandard at four, overpasses at two (Lemma 4.4), and non-overpasses at one (Lemma 4.3). Both lemmas are very compressed. In Lemma 4.4, after choosing for two overpasses R*_alpha and R*_beta the first big vertex b_alpha, b_beta with layer below l1, the proof asserts that if both x_alpha and x_beta are less than x1, then the subpath of R*_beta from R^-_beta to b_beta contains a vertex v at index x_alpha on a layer strictly larger than l_alpha, forcing an edge to b_alpha and violating internal anticompleteness. But no argument is given that the layer of that vertex is > l_alpha; if it is <= l_alpha, the claimed contradiction does not follow, and three overpasses may coexist. Similarly, Lemma 4.3's switch argument assumes the big vertex at the switch index has layer at most l; this is true only if the switching edge's lower endpoint is the big one, which the text does not justify. A missed configuration of this type would allow eight pairwise internally anticomplete paths, giving a wide theta of width 8 and invalidating Lemma 4.1 and hence Theorem 6.1(i).","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a family of graphs G^k_g, built from k paths with cross-edges placed at dyadic indices, and proves Theorem 1.3: for absolute constants L and t0, every G^k_g contains a linear K_k minor model, is W_{t0×t0}- and K_{t0,t0}-induced-minor-free, has girth at least g, has any two vertices of degree at least four at distance at least 2g, and has every outerstring induced subgraph of treewidth at most L. The proof proceeds in three main blocks: a series-parallel contraction argument to rule out large wall induced minors (Section 3), a counting argument showing at most seven pairwise internally anticomplete paths between any two vertices to rule out wide thetas and hence large complete bipartite induced minors (Section 4), and a balanced-separator argument using Korhonen's bounded-degree theorem to bound the treewidth of outerstring induced subgraphs (Section 5).","tokens_in":17346,"tokens_out":33386,"duration_ms":359603,"significance":"If the construction and proofs are correct, this is a valuable contribution: it provides a substantially simpler layered-wheel-like construction than previous ones, and it is the first such construction that simultaneously has arbitrarily large girth and the outerstring-treewidth property, giving a strong counterexample to Trotignon's conjecture. The high-level architecture is clean, the use of external theorems (Grid Theorem, Korhonen's theorem, balanced-separator lemmas, non-outerstring long thetas) is appropriate, and the claimed features (a), (b), and (c) are genuinely notable. The main weaknesses are that several load-bearing combinatorial checks are either omitted or too compressed to be fully verifiable as written.","major_comments":[{"comment":"Lemma 2.2 lists six properties that are load-bearing for Theorem 1.3 and for later lemmas, including the girth lower bound (iii) and the distance bound (v), yet the proof is dismissed with 'the proofs are easy and we leave the details to the reader.' These are not immediate from the construction: for instance, (v) must rule out short paths that use combinations of path segments and switching edges between layers, and (iii) must rule out cycles that use several layers. Please provide complete proofs, or a detailed appendix, for all six items.","section":"Section 2, Lemma 2.2"},{"comment":"The proof of Lemma 4.4 does not justify the key claim that if x_alpha < x_1 and x_beta < x_1, then the subpath of R*_beta from R^-_beta to b_beta contains a vertex v with index x_alpha and layer strictly larger than l_alpha. This is true, but only because b_beta is chosen to have minimal distance to R^-_beta among big vertices with layer below l1; any vertex before b_beta on a layer below l1 would force an earlier big vertex below l1. This argument should be written out. Without it, the conclusion that two overpasses cannot have their chosen big vertices on the same side of x1 is unsupported.","section":"Section 4, Lemma 4.4"},{"comment":"In the proof of Lemma 4.3, the statement 'R* switches layers to l at x' ... It follows that R* includes a big vertex with layer at most l and index x'' needs a justification that the lower endpoint of the switching edge is the big vertex. This follows from Construction 2.1 because cross-layer edges only occur when the lower-layer endpoint has the required dyadic index and is therefore big, but the text should say this explicitly.","section":"Section 4, Lemma 4.3"},{"comment":"Lemma 5.9 concludes that if H is outerstring then H'' has maximum degree less than 9 because the theta just constructed contradicts Lemma 5.6. However, Lemma 5.6 only rules out thetas of length at least 4, while the theta obtained has length at least 2g-1; for g=1,2 this lower bound is 1 or 3, and thetas of length 3 (subdivisions of K_{2,3}) are outerstring. Thus the proof of Lemma 5.1 does not cover g=1,2 as written. This can be repaired by proving Lemma 5.1 for g at least 3 and for smaller g using G^{max(g,3)}_k, since the latter has girth at least g and high-degree vertices at distance at least 2g.","section":"Section 5, Lemma 5.9"}],"minor_comments":[{"comment":"The text repeatedly displays the path length and index bounds as '2k+g' (for example, Construction 2.1 and Figure 2's P_5^64); this should be 2^{k+g}. As typeset, the construction is internally inconsistent.","section":"Throughout, Construction 2.1 and Figure 2"},{"comment":"The sentence 'a in V(D) subseteq G \\ N[b]' should be justified: D is a component of H'\\K', and b is in K', but components of H'\\K' may still have edges to K'; one must use the fact that neighbors of b in H are medium vertices contained in K' or small path-neighbors of degree at most two.","section":"Section 5, Lemma 5.9"},{"comment":"Theorem 6.2 is stated as a strengthening, but its proof is only sketched; consider adding a sentence explaining that it follows from the same separator argument without the outerstring assumption.","section":"Section 6, Theorem 6.2"}],"recommendation":"major_revision","confidential_remarks":"The Section 5 small-g gap is easily fixed by taking the girth parameter to be at least 3, and the seven-path proof in Section 4 is compressed but, on my reading, correct once the minimality argument is supplied. I therefore view this as a major revision rather than a rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"We should know: this is a simple layered-wheel construction that gives the first high-girth counterexample to Trotignon's conjecture, and the proof is in better shape than the stress-test suggests. The family G^k_g is genuinely new in combining arbitrarily large girth, far-apart degree-four vertices, and bounded treewidth for outerstring induced subgraphs. Previous constructions [5],[12],[22] each miss at least one of these. The series-parallel reduction in Section 3 is clean; the balanced-separator argument in Section 5 is careful and the dependence on Korhonen's theorem is legitimate.\n\nThe soft spots are mostly presentational. Lemma 2.2 lists six basic properties—including girth and the distance between big vertices—and dismisses them as 'easy' without proof. For a paper whose selling point is simplicity, that's a small gap in exposition rather than correctness; a referee should ask for a few lines of proof. The constants L, t0, r0 come from cited existential theorems, so no explicit bounds; acceptable for this kind of result.\n\nI checked the stress-test concern about Corollary 4.5. It does not hold up. In Lemma 4.4, the vertex v at index x_alpha lies on the subpath of R*_beta before b_beta, and b_beta is chosen as the first big vertex with layer below l1. Therefore every vertex before b_beta, including v, has layer at least l1, which is strictly larger than l_alpha. That gives the needed adjacency with b_alpha. The construction's switch edges have the big endpoint on the lower layer (the edge rule uses b·2^{k-i+g} with i the lower layer), so the switch endpoint is indeed big. The seven-path bound seems supported.\n\nWho this is for: structural graph theorists working on induced obstructions to treewidth, specifically the layered-wheel program. It is a solid step, not a breakthrough, but it simplifies a crowded topic and refutes a plausible conjecture in a strong form. It deserves a serious referee. My recommendation: send to peer review, with a request to expand the proof of Lemma 2.2 and to double-check the details in Section 4 for the final version.","headline":"Simple new layered-wheel construction with high-girth counterexample to Trotignon's conjecture; the seven-path bound survives scrutiny, though Lemma 2.2 should be expanded.","tokens_in":17927,"tokens_out":13500,"would_cite":true,"duration_ms":133566,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C83","05C75","05C62"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper builds simple layered-wheel-like graphs of unbounded treewidth that simultaneously have arbitrarily large girth and no large outerstring induced subgraph of large treewidth, giving the first high-girth counterexample to…","keywords":["layered wheels","treewidth","induced minors","outerstring graphs","girth","theta","complete bipartite induced minors","series-parallel graphs"],"falsifier":"Look for a concrete failure in the construction: for some $g$ and $k$, find two vertices of degree at least four in $G^k_g$ joined by eight pairwise internally anticomplete paths, which would contradict Corollary 4.5 and break the proof of Lemma 4.1; alternatively, exhibit an induced subgraph of $G^k_g$ that is outerstring and has treewidth greater than the paper's $L$.","tokens_in":16857,"feed_emoji":"🧩","tokens_out":11489,"duration_ms":109783,"temperature":0.7,"pith_summary":"This paper produces a family of graphs, one for each pair of parameters $(g,k)$, whose treewidth grows with $k$ while their girth grows with $g$. The graphs are built from $k$ long paths stacked in layers, with sparse cross-edges placed at carefully chosen indices, so each graph contains a large complete minor whose branching sets are paths. The main theorem shows these graphs contain no large wall and no large complete bipartite graph as an induced minor, keep all vertices of degree at least four far apart, and have the property that every induced subgraph that is an outerstring graph has treewidth bounded by an absolute constant. Because $g$ can be chosen freely, the construction is the first counterexample to Trotignon's conjecture that can also be made to have arbitrarily large girth. The upshot is that the layered-wheel-like obstruction to bounded treewidth persists even in very sparse, high-girth graphs.","feed_headline":"High-girth graphs refute Trotignon's treewidth conjecture","feed_subtitle":"A simple layered construction keeps treewidth unbounded while every outerstring piece stays small.","key_machinery":"The central object is the layered-wheel-like graph $G^k_g$, built from $k$ paths $P_1,\\ldots,P_k$ of length $2k+g$, with cross edges only between equal-index vertices $P_i^x$ and $P_j^x$ when $x=b\\cdot 2^{k-j+g}$ for an odd integer $b$; the paths are the branching sets of a linear complete minor model of $K_k$. The proof runs on three mechanisms. First, an induced-subgraph contraction step: after contracting, for each big vertex, the medium vertices attached to it, every induced subgraph becomes a subgraph of a series-parallel graph (a graph of treewidth at most two built by series and parallel compositions), which rules out large wall induced minors. Second, a path-counting step: between any two big vertices there are at most four nonstandard paths, at most two overpasses, and at most one standard non-overpass, yielding at most seven internally anticomplete paths and, through a wide-$\\theta$ lemma, ruling out large complete bipartite induced minors. Third, a separator-lifting step: for an outerstring induced subgraph $H$, a contracted minor $H''$ is bipartite with maximum degree at most $8$ unless $H$ already contains a long $\\theta$, and $H''$ inherits the absence of large walls; a bounded-degree grid theorem bounds $\\operatorname{tw}(H'')$, and balanced separators are lifted back to bound $\\operatorname{tw}(H)$.","core_discovery":"The central claim is Theorem 1.3: there exist absolute constants $L$ and $t_0$ such that for all $g,k$ there is a graph $G^k_g$ with a linear model of $K_k$ (so treewidth at least $k-1$), no $W_{t_0\\times t_0}$ or $K_{t_0,t_0}$ as an induced minor, vertices of degree at least four pairwise at distance at least $2g$, girth at least $g$, and every induced subgraph that is an outerstring graph has treewidth at most $L$. The construction is explicit: take $k$ paths $P_1,\\ldots,P_k$ of length $2k+g$, and join vertices $P_i^x$ and $P_j^x$ exactly when $x=b\\cdot 2^{k-j+g}$ for odd $b$. The proof is carried by three structural facts: after contracting all medium vertices around big vertices every induced subgraph becomes series-parallel, any two big vertices are joined by at most seven internally anticomplete paths, and any induced subgraph of treewidth larger than $L$ contains a long $\\theta$ of length at least $2g-1$. Since long thetas are not outerstring graphs, this gives the outerstring treewidth bound. Thus the graph family is a layered-wheel-like obstruction with arbitrarily large girth, and it refutes Trotignon's conjecture in the stronger high-girth sense.","pith_inferences":["The seven-path bound is probably not tight: the paper notes the argument can be refined to a tight bound of three paths, so a closer case analysis of $G^k_g$ for small $g,k$ should pin down the true maximum number of internally anticomplete paths between two big vertices.","Because the construction is so sparse, it suggests any complete induced-subgraph analog of the grid theorem must be able to express obstructions that are locally tree-like and globally wheel-like; this is an implicit consequence, not stated by the paper.","The separator-lifting argument used here may extend to earlier layered-wheel constructions: if those graphs also have an induced minor of bounded degree and bounded treewidth, the same balancing argument would establish the outerstring property for them as well; this is a testable extension the paper does not pursue."],"forward_implications":["For every prescribed girth $g$, the construction supplies a graph of treewidth at least $k-1$ that still excludes a fixed wall and a fixed complete bipartite graph as induced minors, so the layered-wheel-like obstruction is compatible with arbitrarily high girth.","Every induced subgraph of $G^k_g$ with treewidth larger than $L$ contains a theta of length at least $2g-1$; hence within this family, large treewidth is witnessed by a long theta, and long thetas are never outerstring graphs.","No earlier layered-wheel construction had all three features at once; this one simultaneously separates high-degree vertices, forbids short cycles, and keeps every outerstring piece small.","The absolute constants $t_0$ and $L$ do not depend on $g$ or $k$, so the counterexample to Trotignon's conjecture is uniform: one fixed exclusion size and one fixed outerstring treewidth bound work at every scale."],"supporting_citations":[{"why":"Supplies the grid theorem: every graph of large treewidth contains a subdivision of a large wall, framing why excluding walls is the relevant obstruction.","marker":"[21]"},{"why":"Supplies the structural dichotomy reducing treewidth obstructions to linear complete minor models, and the wide-theta lemma used to rule out complete bipartite induced minors.","marker":"[10]"},{"why":"Bounds the treewidth of bounded-degree graphs with no large wall subdivision or wall line graph as induced subgraph; used to bound the treewidth of $H''$.","marker":"[18]"},{"why":"Implicitly proves that long thetas are not outerstring graphs, which converts the long-theta statement into the outerstring treewidth bound.","marker":"[15]"},{"why":"Provides the lemma turning large wall induced minors into induced subgraphs that are wall subdivisions or their line graphs, used in the no-wall proof.","marker":"[1]"},{"why":"One of the prior layered-wheel constructions, the theta-free one, which achieved large girth; the comparison baseline for the new features.","marker":"[22]"},{"why":"The previous construction that already refuted Trotignon's conjecture but lacked large girth and simplicity; the comparison point for the first high-girth counterexample.","marker":"[5]"},{"why":"The conjecture being refuted: large treewidth with the stated excluded induced minors would force an outerstring induced subgraph of large treewidth.","marker":"[23]"}],"fun_headline_variants":["Simple layered wheels refute Trotignon's conjecture","High-girth refutation of Trotignon's treewidth conjecture","First high-girth counterexample to Trotignon's conjecture","Simple construction contradicts Trotignon's treewidth conjecture","Layered wheels: huge treewidth, arbitrarily large girth"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof that no large complete bipartite induced minor appears rests on the case analysis in Section 4, and specifically on the claim that any two big vertices are joined by at most seven pairwise internally anticomplete paths; if some overlooked routing of overpass or non-overpass paths produced an eighth such path, the $K_{t_0,t_0}$-exclusion would fail.","fun_headline_variants_meta":{"raw":{"variants":["Simple layered wheels refute Trotignon's conjecture","High-girth refutation of Trotignon's treewidth conjecture","First high-girth counterexample to Trotignon's conjecture","Simple construction contradicts Trotignon's treewidth conjecture","Layered wheels: huge treewidth, arbitrarily large girth"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000616,"raw_usage":{"total_tokens":2952,"prompt_tokens":1127,"completion_tokens":1825,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":743,"completion_tokens_details":{"reasoning_tokens":1746}},"tokens_in":743,"tokens_out":1825,"duration_ms":16614,"temperature":1.0,"reasoning_tokens":1746,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T19:10:21.608030+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Look for a concrete failure in the construction: for some $g$ and $k$, find two vertices of degree at least four in $G^k_g$ joined by eight pairwise internally anticomplete paths, which would contradict Corollary 4.5 and break the proof of Lemma 4.1; alternatively, exhibit an induced subgraph of $G^k_g$ that is outerstring and has treewidth greater than the paper's $L$.","supporting_citations":[{"cited_title":"Graph minors. V. Excluding a planar graph","cited_arxiv_id":null,"evidence_quote":"Supplies the grid theorem: every graph of large treewidth contains a subdivision of a large wall, framing why excluding walls is the relevant obstruction."},{"cited_title":"Induced subgraphs and tree decompositions XVI. Complete bipartite induced minors","cited_arxiv_id":null,"evidence_quote":"Supplies the structural dichotomy reducing treewidth obstructions to linear complete minor models, and the wide-theta lemma used to rule out complete bipartite induced minors."},{"cited_title":"Grid induced minor theorem for graphs of small degree","cited_arxiv_id":null,"evidence_quote":"Bounds the treewidth of bounded-degree graphs with no large wall subdivision or wall line graph as induced subgraph; used to bound the treewidth of $H''$."},{"cited_title":"Coloring polygon visibility graphs and their generalizations","cited_arxiv_id":null,"evidence_quote":"Implicitly proves that long thetas are not outerstring graphs, which converts the long-theta statement into the outerstring treewidth bound."},{"cited_title":"On the tree-width of even-hole-free graphs","cited_arxiv_id":null,"evidence_quote":"Provides the lemma turning large wall induced minors into induced subgraphs that are wall subdivisions or their line graphs, used in the no-wall proof."},{"cited_title":"(Theta, triangle)-free and (even hole,K4)-free graphs. Part 1: Layered wheels","cited_arxiv_id":null,"evidence_quote":"One of the prior layered-wheel constructions, the theta-free one, which achieved large girth; the comparison baseline for the new features."},{"cited_title":"Trotignon","cited_arxiv_id":null,"evidence_quote":"The conjecture being refuted: large treewidth with the stated excluded induced minors would force an outerstring induced subgraph of large treewidth."}],"review_version":1}