{"id":"7dc46263-d3a4-47fd-a03e-9641c2f718ef","arxiv_id":"2507.12697","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Every graph of large rank-depth contains a pivot-minor isomorphic to a long path or to two cliques joined by a half-graph, resolving a 2021 conjecture.","lead":"A new theorem shows that every graph with sufficiently large rank-depth must contain one of two specific pivot-minors: a long path, or two large cliques joined by a half-graph. This settles an open problem from 2021 on dense analogs of tree-depth and sharpens the structural theory of pivot-minor-closed graph classes.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3.8's proof assumes every path in a flipped graph is a subpath of the underlying path; cross-row flip edges make this false, so Corollary 3.9's reduction is not established.","rationale":"The reader's conditional verdict is reasonable, but I do not think the weakest assumption is the external Mahlmann theorem. That dependency is explicit and unavoidable; Theorem 1.5 is advertised as relying on it. The internal weak point I found is in the proof of Lemma 3.8, the tool behind Corollary 3.9. Under the paper's own definition of a P-flip, a path in G can use flip edges between non-adjacent parts, so the proof's opening assertion that such a path is a subpath of the underlying mPn is false. I give an explicit 3-part configuration satisfying the lemma's hypotheses where the assertion fails. This does not disprove the main theorem; the lemma and Corollary 3.9 may still be true, and a computational check can test that. But as written, Section 3's reduction is missing a case. The final theorem therefore remains conditional on a repair of Lemma 3.8 or on a different argument, in addition to the acknowledged dependence on Mahlmann's theorem.","tokens_in":15744,"tokens_out":27652,"duration_ms":300912,"concrete_test":"Check Lemma 3.8 on the explicit configuration m=1, n=3, P={X,Y,Z} the three column classes, and F the symmetric set with diagonals and (X,Y),(Y,Z) in F but (X,Z) not in F. Determine whether the claimed (k-1)-flipped P3 pivot-minor exists in the resulting flip of 3P3. More systematically, exhaustively enumerate all symmetric F on P for m=1 and n=3 and n=4, and test whether every graph satisfying Lemma 3.8's hypotheses contains the asserted pivot-minor. A counterexample would refute the lemma; a collection of successes would show that the proof needs a missing argument covering non-underlying paths, and the paper would need that argument before Corollary 3.9 can be accepted.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The proof of Theorem 1.5 funnels through Corollary 3.9, which is proved using Lemma 3.8. The first sentence of the proof of Lemma 3.8 asserts that a P-path Q in the flipped graph G from X to X1 with (X,X1) not in F is automatically a subpath of (m+2)Pn. This does not follow from the definition of a P-flip: an edge between parts Y and Z can be present in G even when it is not an edge of (m+2)Pn, namely when (Y,Z) is in F. Cross-row edges of this kind can form such a path. Example: take m=1, n=3, P the three column classes X,Y,Z, and F the symmetric set with diagonals and (X,Y),(Y,Z) present but (X,Z) absent. Then (1,1)-(2,2)-(3,3) is a path in G from X to Z with (X,Z) not in F, yet it is not a subpath of 3P3. The induction in Lemma 3.8 uses that internal vertices have degree 2 and that path replacement happens inside the underlying path; both fail for this example. Unless 'P-path' has an undeclared restricted meaning, Lemma 3.8's proof breaks at its first step, and Corollary 3.9 is unsupported as written.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves Theorem 1.5: there is a function f such that every graph of rank-depth at least f(t) has a pivot-minor isomorphic to the t-vertex path P_t or to the graph K_t m K_t obtained from two disjoint t-cliques by adding a half graph. The proof follows the announced plan: invoke Mählmann's characterization of unbounded rank-depth by four induced subgraphs, handle the two half-graph cases with known lemmas, then devote Sections 3 and 4 to showing that a flipped sP_s contains a 1-flip of a long path, and that a sufficiently long 1-flip of a path contains P_t as a pivot-minor. Section 5 assembles these ingredients into Theorem 1.5.","tokens_in":16031,"tokens_out":14216,"duration_ms":160961,"significance":"If the proof is correct, the theorem resolves the 2021 conjecture of Kwon, McCarty, Oum, and Wollan and yields the forbidden-pivot-minor characterization of pivot-minor-closed classes of bounded rank-depth. It would also recover the vertex-minor theorem for paths and the known matroid branch-depth consequence. The plan is well motivated, the organization is clear, and much of the secondary material (the arithmetic in Proposition 4.1, Lemma 4.4, and the use of Corollary 4.6) is carefully executed. The main weakness is in Section 3: the reduction from flipped mP_n to 1-flips of P_n, which is the bridge to the rest of the proof, is not established as written.","major_comments":[{"comment":"The first sentence of the proof asserts that a union-of-parts path Q from X to X1 with (X,X1) not in F is automatically a subpath of (m+2)P_n. This is false. Take m=1, n=3, let P={X,Y,Z} be the three columns of 3P_3, and let F be the symmetric set containing (X,X), (Y,Y), (Z,Z), (X,Y), (Y,Z) and their reverses, but not (X,Z). In the flipped graph G=(3P_3)⊕(P,F), the vertices (1,1), (2,2), (3,3) form a path from X to Z with (X,Z) not in F, and in fact it is a shortest such path because there is no direct edge between the columns X and Z. This path is not a subpath of 3P_3, and its internal vertex (2,2) does not have degree 2 in G. Thus the stated path-replacement induction in Lemma 3.8 is not valid, and the conclusion of the lemma is not proved.","section":"Section 3, Lemma 3.8"},{"comment":"The proof of Corollary 3.9 uses the same erroneous principle. It chooses a shortest subpath Q1 of the first row of (m+4)P_n between X1 and X2 and says that if (X1,X2) is not in F, then Q1 is a path of G. But edges of Q1 may be deleted by the flip: if an edge of Q1 joins parts Y and Z with (Y,Z) in F, then that edge is absent from G even though it is an edge of (m+4)P_n. For example, if F contains (X1,Y) and (Y,X2) but not (X1,X2), then the first-row subpath X1-Y-X2 is not a path in G. Therefore the contrapositive use of Lemma 3.8 and the subsequent reduction to the case L_F(X1,X2)∪R_F(X1,X2)≠∅ are unsupported. Since Proposition 3.4 is proved by iterating Corollary 3.9, Proposition 3.4 is also not established as written.","section":"Section 3, Corollary 3.9"},{"comment":"The proof of Theorem 1.5 in Section 5 depends essentially on Proposition 3.4 to convert a flipped sP_s into a 1-flip of P_n. Because the proof of Proposition 3.4 rests on the invalid arguments in Lemma 3.8 and Corollary 3.9, the main theorem is not supported by the current manuscript. A repair of the Section 3 reduction is needed before the rest of the argument can be assessed.","section":"Section 5"}],"minor_comments":[{"comment":"For t=1 the definition n:=3(2t^2-t-1) gives n=0 and s=4n-3=-3, so the function g is evaluated outside its domain N; the case t=1 should be handled separately (it is trivial, since every graph has P_1 as a pivot-minor).","section":"Section 5, proof of Theorem 1.5"},{"comment":"The inequality s ≥ 3/2 t + 1 should be stated with integer ceilings, e.g. s ≥ ceil(3t/2+1), because s and t are integers; the current wording is ambiguous. The intended quantifier is clear from the proof, but the statement should be made precise.","section":"Section 4, Lemma 4.4"}],"recommendation":"major_revision","confidential_remarks":"The gap in Section 3 is load-bearing, but I do not see a counterexample to the main theorem or even to the statements of Lemma 3.8 and Corollary 3.9; the issue is that the provided proofs are invalid. The paper would need a substantially reworked Section 3 before the result can be accepted. I would not recommend rejection on the current evidence, but the authors should be asked to supply a correct proof of Proposition 3.4 or to revise the strategy."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Good to see the conjecture settled, but the current proof has a load-bearing gap that needs to be addressed before I'd trust the reduction. The paper answers the Kwon–McCarty–Oum–Wollan conjecture by proving that large rank-depth forces Pt or Kt m Kt as a pivot-minor. The high-level strategy is sensible: invoke Mahlmann's induced-subgraph characterization, then show each outcome yields the desired pivot-minor. The treatment of Ks m Ks and Ks m Ks via earlier lemmas is clean, and the arithmetic in Proposition 4.1 checks out. The soft spot is Lemma 3.8, which is essential for Corollary 3.9 and hence for Proposition 3.4. The first sentence of the proof asserts that a P-path Q from X to X1 with (X,X1) not in F is automatically a subpath of (m+2)Pn. That is false. In a P-flip, edges between parts can exist when the pair is in F even if the underlying path has no such edge. For instance, with m=1, n=3 and P the three column classes X,Y,Z, take F with diagonals and (X,Y),(Y,Z) but not (X,Z). Then (1,1)-(2,2)-(3,3) is a path in the flipped graph from X to Z, and it is not a subpath of 3P3. The proof's induction then has nothing to stand on. The stress-test note is right: Corollary 3.9 is unsupported as written. The reader's concern about Lemma 4.4 is minor by comparison—the proof omits residues 2 and 5, but the specific s used in Proposition 4.1 avoids them, so a final version can tighten the statement. The dependence on Mahlmann's recent characterization is real but not improper; it is an independent external result. This is a strong paper that deserves a serious referee, but as it stands the main theorem lacks a sound proof. I'd send it to review with a directive to fix Lemma 3.8 or explain why the claimed subpath property holds under the lemma's hypotheses.","headline":"The conjecture is settled in spirit, but the proof of Lemma 3.8 has a load-bearing gap that leaves Corollary 3.9 unsupported as written.","tokens_in":16559,"tokens_out":4028,"would_cite":false,"duration_ms":40515,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C83","05C75"],"pacs":[],"model":"deepseek-v4-flash","headline":"A graph with sufficiently large rank-depth always contains a path on $t$ vertices or two disjoint $t$-cliques joined by a half graph as a pivot-minor.","keywords":["rank-depth","pivot-minors","vertex-minors","shrub-depth","half graph","graph minors","dense graphs","binary matroids"],"falsifier":"The claim would fail if any graph of rank-depth at least $f(4)$ had neither a $P_4$ nor a $K_4 \\boxtimes K_4$ pivot-minor, so an exhaustive pivot-minor search over graphs up to that threshold is a concrete check; alternatively, a counterexample to the cited classification at $s=4$ or $s=5$ would remove the proof's foundation.","tokens_in":15543,"feed_emoji":"🕸️","tokens_out":8405,"duration_ms":85063,"temperature":0.7,"pith_summary":"The paper proves a structural dichotomy for dense graphs: for every positive integer $t$ there is a threshold $f(t)$ such that every graph with rank-depth at least $f(t)$ has a pivot-minor equal to a $t$-vertex path $P_t$ or to $K_t \\boxtimes K_t$, the graph made from two disjoint $t$-cliques joined by a half graph. This is exactly the pair of obstructions that was conjectured to characterize bounded rank-depth in pivot-minor-closed classes. Because every vertex-minor is a pivot-minor, the statement also recovers the known path-obstruction theorem for vertex-minor-closed classes. If the dichotomy holds, a pivot-minor-closed class of graphs has bounded rank-depth precisely when it excludes some $P_t$ and some $K_t \\boxtimes K_t$.","feed_headline":"Every large-rank-depth graph hides a path or a half-joined twin clique","feed_subtitle":"Long paths and half-joined twin cliques are the only pivot-minor obstructions to bounded rank-depth.","key_machinery":"The engine is the pivoting formula of Lemma 2.1, which describes pivoting an edge as a triple of symmetric-difference flips between the common-neighbor set, the left-neighbor set, and the right-neighbor set, followed by exchanging the endpoints. With it, the paper proves a reduction lemma (Lemma 3.5) showing that pivoting along an edge between two flip-parts preserves the flipped structure of the surviving rows, with the flip relation updated by the symmetric difference $D_F(X,X')$. Iterating this reduction via Corollary 3.9 peels a flipped multi-path down to a $1$-flip of a single path, and the path lemmas in Section 4 then use the same pivot formula to shorten and extract a prescribed path $P_t$.","core_discovery":"The central discovery is that rank-depth, the dense analogue of tree-depth, is controlled by just two unavoidable pivot-minors: long paths and half-graph-joined twin cliques. Starting from the known induced-subgraph classification of large rank-depth, according to which any such graph contains one of three half-graph hybrids or a flipped multi-path, the proof transforms each alternative into the desired pivot-minor. The two hard transformations are: every flipped copy of many disjoint paths contains a $1$-flip of a single long path as a pivot-minor, and every $1$-flip of a sufficiently long path contains a short path $P_t$ as a pivot-minor. Along the way the paper proves a stronger version, Proposition 3.4, that controls how many parts of the flip can be removed by each pivoting move.","pith_inferences":["The proof's threshold $f(t)$ is built from the cited classification function and is likely enormous; a natural next step is to determine whether $f(t)$ can be taken polynomial in $t$, which would give an algorithmically usable rank-depth obstruction test.","The local, row-by-row nature of the pivoting reductions suggests that similar peeling arguments might apply to other vertex-minor or pivot-minor based width parameters, though the paper does not claim this.","The pair of obstructions separates a path-like regime from a half-graph-like dense regime, which hints that rank-depth may interact with model-theoretic notions such as stability in graph classes that forbid one of the two structures."],"forward_implications":["A pivot-minor-closed class has bounded rank-depth exactly when it excludes some path $P_t$ and some half-joined twin clique $K_t \\boxtimes K_t$; the two families are both necessary, since each can be avoided by the other side of the dichotomy.","Because every vertex-minor is a pivot-minor, the theorem implies the earlier vertex-minor obstruction theorem for bounded rank-depth.","The same dichotomy transfers to binary matroids: every binary matroid of sufficiently large branch-depth has the cycle matroid of a large fan graph as a minor, via the pivot-minor and matroid-minor correspondence.","Bounded shrub-depth classes are covered as well, because a class of graphs has bounded shrub-depth exactly when it has bounded rank-depth."],"supporting_citations":[{"why":"Supplies the induced-subgraph classification of large rank-depth: every such graph contains $K_s \\boxtimes K_s$, its complement, the other half-graph hybrid, or a flipped $sP_s$; this is the starting point of the proof.","marker":"[12]"},{"why":"Supplies the pivot formula used in every reduction of Sections 3 and 4, describing an edge pivot as a triple of flips followed by an endpoint exchange.","marker":"[14]"},{"why":"Formulated the conjecture answered in the paper, and provides the fact that $K_t \\boxtimes K_t$ has no $P_5$ pivot-minor.","marker":"[10]"},{"why":"Shows that $K_t \\boxtimes K_t$ has a $P_{t+1}$ pivot-minor, handling one of the alternatives in the classification.","marker":"[7]"},{"why":"Shows that the complement of the half-graph hybrid has a $P_{2t}$ pivot-minor, handling another alternative.","marker":"[11]"},{"why":"Provides the reduction lemma for $(s,t)$-paths used to shorten $1$-flips of long paths into short paths.","marker":"[9]"},{"why":"Defines rank-depth, proves it is monotone under vertex-minors, and proves its equivalence to shrub-depth, so the main theorem carries over to shrub-depth.","marker":"[2]"}],"fun_headline_variants":["High rank-depth guarantees a path or half-joined cliques","Rank-depth's unavoidable pivot-minors: paths and half-joined cliques","Large rank-depth graphs always hide a path or twin cliques","Only two pivot-minors block bounded rank-depth"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument rests on the cited induced-subgraph classification of large rank-depth and on the pivot formula of Lemma 2.1, used in every pivoting step; if either is incorrect, the main theorem does not follow.","fun_headline_variants_meta":{"raw":{"variants":["High rank-depth guarantees a path or half-joined cliques","Rank-depth's unavoidable pivot-minors: paths and half-joined cliques","Large rank-depth graphs always hide a path or twin cliques","Only two pivot-minors block bounded rank-depth"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000669,"raw_usage":{"total_tokens":2968,"prompt_tokens":778,"completion_tokens":2190,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":394,"completion_tokens_details":{"reasoning_tokens":2119}},"tokens_in":394,"tokens_out":2190,"duration_ms":17769,"temperature":1.0,"reasoning_tokens":2119,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T16:42:49.683824+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"The claim would fail if any graph of rank-depth at least $f(4)$ had neither a $P_4$ nor a $K_4 \\boxtimes K_4$ pivot-minor, so an exhaustive pivot-minor search over graphs up to that threshold is a concrete check; alternatively, a counterexample to the cited classification at $s=4$ or $s=5$ would remove the proof's foundation.","supporting_citations":[{"cited_title":"52nd Int","cited_arxiv_id":null,"evidence_quote":"Supplies the induced-subgraph classification of large rank-depth: every such graph contains $K_s \\boxtimes K_s$, its complement, the other half-graph hybrid, or a flipped $sP_s$; this is the starting point of the proof."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the pivot formula used in every reduction of Sections 3 and 4, describing an edge pivot as a triple of flips followed by an endpoint exchange."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Formulated the conjecture answered in the paper, and provides the fact that $K_t \\boxtimes K_t$ has no $P_5$ pivot-minor."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Shows that $K_t \\boxtimes K_t$ has a $P_{t+1}$ pivot-minor, handling one of the alternatives in the classification."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Shows that the complement of the half-graph hybrid has a $P_{2t}$ pivot-minor, handling another alternative."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the reduction lemma for $(s,t)$-paths used to shorten $1$-flips of long paths into short paths."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines rank-depth, proves it is monotone under vertex-minors, and proves its equivalence to shrub-depth, so the main theorem carries over to shrub-depth."}],"review_version":1}