Pith. sign in

REVIEW 3 major objections 2 minor 18 references

Unavoidable pivot-minors in graphs of large rank-depth

T0 review · 3 major / 2 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2507.12697 v1 pith:DCCK4TCA submitted 2025-07-17 math.CO

Jungho Ahn , Kevin Hendrey , O-joung Kwon , Sang-il Oum This is my paper · ORCID
classification math.CO MSC 05C8305C75
keywords rank-depthpivot-minorsvertex-minorsshrub-depthhalfgraphminorsdensegraphsbinarymatroids
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 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$.

What carries the argument

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$.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

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

  • 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.
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

3 major / 2 minor

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.

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 (3)
  1. [Section 3, Lemma 3.8] 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.
  2. [Section 3, Corollary 3.9] 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.
  3. [Section 5] 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.
minor comments (2)
  1. [Section 5, proof of Theorem 1.5] 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).
  2. [Section 4, Lemma 4.4] 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.

Circularity Check

0 steps flagged · score 2.0 of 10

No circular derivation: proof reduces to Mahlmann's external theorem and prior published lemmas; self-citations are not load-bearing. A proof gap in Lemma 3.8 is a correctness risk, not circularity.

full rationale

No circular step is identifiable in the derivation chain. Theorem 1.5 is obtained by applying Mahlmann's theorem (Theorem 3.1, [12,13]) to a graph of large rank-depth, and then eliminating the four listed induced-subgraph alternatives: K_s m K_s is already the desired pivot-minor; the complemented half-graph cases are handled by Lemmas 3.2-3.3, which are prior published results of other (partially overlapping) author teams with proofs independent of the present theorem; the flipped-sP_s case is reduced to a 1-flip of a path (Proposition 3.4) and then to P_t (Proposition 4.1). Each lemma is proved from the pivot formula (Lemma 2.1, Oum [14]) and the flip definitions; none of the displayed equations identifies the target as its own input. The self-citations to [2,7,9,10,11,14] are numerous but are prior peer-reviewed theorems whose assumptions do not include the target result, and the keystone external input is Mahlmann's theorem, by an independent author, so the cited results are real evidence rather than a self-citation loop. The one substantive concern is in Lemma 3.8, whose first sentence asserts, without proof, that a P-path Q in the flipped graph avoiding an F-pair between its ends must be a subpath of (m+2)P_n; a reviewer's counterexample suggests this may be false, which would invalidate Corollary 3.9 and the Section 3 reduction. That is a correctness risk (an omitted justification), not a circularity: it does not make the theorem reduce by definition or by a fitted parameter to its inputs. Accordingly the circularity score is 2, reflecting only the presence of non-load-bearing self-citations.

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

The central claim rests on two classes of imported results: Mahlmann's recent characterization and several pivot-minor lemmas from the literature. None of the imported results is the target theorem, and no fitted parameters appear.

assumptions (5)
  • domain assumption Mahlmann's induced-subgraph characterization (Theorem 3.1): every graph of rank-depth at least g(s) has an induced subgraph isomorphic to K_s m K_s, K_s m K_s, K_s m K_s, or a flipped sP_s.
    Imported from [12,13]; it is the keystone external result and is not proved in the paper.
  • standard math Pivot formula Lemma 2.1 (Oum [14]) describing G^uv via C,L,R and three complementations.
    Stated without proof in Section 2.1; used in Lemma 3.5 and throughout the pivoting reductions.
  • standard math Lemma 3.2: K_t m K_t has a pivot-minor isomorphic to P_{t+1} [7].
    Used in Theorem 1.5 to handle one of Mahlmann's four induced subgraph cases.
  • standard math Lemma 3.3: K_t m K_t has a pivot-minor isomorphic to P_{2t} [11].
    Used to handle another of the four induced subgraph cases.
  • standard math Lemma 4.3 (Kim-Oum [9]): every (s,t)-path with t>=6 has an (s-2,t-6)-path as pivot-minor.
    Used in Lemma 4.4 to reduce long paths to shorter paths.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Unavoidable pivot-minors in graphs of large rank-depth." pith.science (2026). https://pith.science/paper/DCCK4TCA

@misc{pith2026250712697,
  author       = {Pith},
  title        = {Pith review of: Unavoidable pivot-minors in graphs of large rank-depth},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DCCK4TCA}},
  note         = {Machine review of arXiv:2507.12697}
}
abstract

Shrub-depth and rank-depth are related graph parameters that are dense analogs of tree-depth. We prove that for every positive integer $t$, every graph of sufficiently large rank-depth contains a pivot-minor isomorphic to a path on $t$ vertices or a graph consisting of two disjoint cliques of size $t$ joined by a half graph. This answers an open problem raised by Kwon, McCarty, Oum, and Wollan in 2021.

Figures

Figures reproduced from arXiv: 2507.12697 by the authors.

Figure 1
Figure 1. The graph K4 m K4. analog of tree-width, which was introduced by Oum and Seymour [15]. Linear rank-width of graphs is a dense analog of path-width and is a linearized version of rank-width, see [1]. Rank-depth of graphs is a dense analog of tree-depth, which was introduced by DeVos, Kwon, and Oum [2]. Shrub-depth was introduced earlier by Ganian, Hlinˇen´y, Neˇsetˇril, Obdrˇz´alek, Ossona de Mendez, and Ramadurai [4… view at source ↗
Figure 2
Figure 2. An example of the case pX, Xq R F in Lemma 3.7 where F consists of pX, X1q, pX, X2q, pX1, X2q, pX1, X1q and their reverses. Note that CF pX, X1q “ tX1, X2u and RF pX, X1q “ tXu. One can observe that F△DF pX, X1q contains no pair pX, X1 q for any X1 P P, and G1 “ pmPnq ‘ pP|m,pF△DF pX, X1qq|mq. then G contains a pk ´ 1q-flipped mPn as a pivot-minor. Lemma 3.7. For integers m, n ě 1, let P be a coarsening of the colum… view at source ↗
Figure 3
Figure 3. An example of G1 in the induction statement in Lemma 3.8 when ℓ “ 2. Observe that X2 P LF pX, X1 q, and both pX2 , Xq and pX2 , X1 q are contained in F△DF pX, X1 q. Also, pX, X1 q P F△DF pX, X1 q. In this case, we obtain a coarsening of P by merging X and X1 . Proof. Since Q is a Ť P-path in G from X to X1 and pX, X1 q R F, it is a subpath of pm ` 2qPn. We may assume that Q is a subpath of the pm ` 2q-th row of pm `… view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: An example of G1 in the induction statement in Lemma 3.8 when ℓ “ 3. In this case, we first pivot u1u2 and then pivot u 1 1u3 to obtain G˚ . Let P0 :“ pPztX, X1 uq Y tX Y X1 u. Let F0 be the set obtained from F by removing all pairs which contain X or X1 and adding the…
Figure 5
Figure 5. Figure 5: The graph G in Lemma 4.2 for P “ u1u2 ¨ ¨ ¨ u10, a “ u4, and b “ u8 where the bottom vertices are the vertices in X. Edges between non-consecutive bottom vertices are not shown. We remark that G ^ u4u8 ´ tu4, u8u is the tu1, u10u-flip of P8, which is a cycle of length …

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

  1. [1]

    Farley, and Andrzej Proskurowski, Obstructions for linear rank-width at most 1, Discrete Appl

    Isolde Adler, Arthur M. Farley, and Andrzej Proskurowski, Obstructions for linear rank-width at most 1, Discrete Appl. Math. 168 (2014), 3–13

    work page 2014

  2. [2]

    Matt DeVos, O-joung Kwon, and Sang-il Oum, Branch-depth: Generalizing tree-depth of graphs , European J. Combin. 90 (2020), 103186, 23. MR 4129026

    work page 2020

  3. [3]

    Methods Comput

    Robert Ganian, Petr Hlinˇ en´ y, Jaroslav Neˇ setˇ ril, Jan Obdrˇ z´ alek, and Patrice Ossona de Mendez, Shrub-depth: Capturing height of dense graphs , Log. Methods Comput. Sci. 15 (2019), no. 1, 7:1–7:25

    work page 2019

  4. [4]

    Sci., vol

    Robert Ganian, Petr Hlinˇ en´ y, Jaroslav Neˇ setˇ ril, Jan Obdrˇ z´ alek, Patrice Ossona de Mendez, and Reshma Ramadurai, When trees grow low: shrubs and fast MSO1, Mathematical foundations of computer science 2012, Lecture Notes in Comput. Sci., vol. 7464, Springer, Heidelberg, 2012, pp. 419–430. MR 3030450

    work page 2012

  5. [5]

    Jim Geelen, O-joung Kwon, Rose McCarty, and Paul Wollan, The grid theorem for vertex-minors, J. Combin. Theory Ser. B 158 (2023), 93–116

    work page 2023

  6. [6]

    Pascal Gollin, Kevin Hendrey, Dillon Mayhew, and Sang-il Oum, Obstructions for bounded branch-depth in matroids , Adv

    J. Pascal Gollin, Kevin Hendrey, Dillon Mayhew, and Sang-il Oum, Obstructions for bounded branch-depth in matroids , Adv. Comb. (2021), Paper No. 4, 25. MR 4269799

    work page 2021

  7. [7]

    Petr Hlinˇ en´ y, O-joung Kwon, Jan Obdrˇ z´ alek, and Sebastian Ordyniak,Tree-depth and vertex- minors, European J. Combin. 56 (2016), 46–56. MR 3490094

    work page 2016

  8. [8]

    Vertex-minor obstructions , European J

    Mamadou Moustapha Kant´ e and O-joung Kwon,Linear rank-width of distance-hereditary graphs II. Vertex-minor obstructions , European J. Combin. 74 (2018), 110–139

    work page 2018

Show all 18 references
  1. [9]

    Jaehoon Kim and Sang-il Oum, The Erd˝ os-Hajnal property for graphs with no fixed cycle as a pivot-minor, Electron. J. Combin. 28 (2021), #P2.9

    2021

  2. [10]

    O-joung Kwon, Rose McCarty, Sang-il Oum, and Paul Wollan, Obstructions for bounded shrub- depth and rank-depth , J. Combin. Theory Ser. B 149 (2021), 76–91

    2021

  3. [11]

    O-joung Kwon and Sang-il Oum, Unavoidable vertex-minors in large prime graphs , European J. Combin. 41 (2014), 100–127

    2014

  4. [12]

    52nd Int

    Nikolas M¨ ahlmann,Forbidden induced subgraphs for bounded shrub-depth and the expressive power of MSO, Proc. 52nd Int. Coll. on Automata, Languages, and Programming (ICALP 2025), LIPIcs. Leibniz Int. Proc. Inform., vol. 334, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 20...

    2025

  5. [13]

    , Forbidden induced subgraphs for bounded shrub-depth and the expressive power of MSO , arXiv:2501.13903, 2025

    2025 arXiv

  6. [14]

    Sang-il Oum, Rank-width and vertex-minors , J. Combin. Theory Ser. B 95 (2005), no. 1, 79–100. MR 2156341

    2005

  7. [15]

    Sang-il Oum and Paul Seymour, Approximating clique-width and branch-width, J. Combin. Theory Ser. B 96 (2006), no. 4, 514–528

    2006

  8. [16]

    Neil Robertson and Paul Seymour, Graph minors. I. Excluding a forest , J. Combin. Theory Ser. B 35 (1983), no. 1, 39–61. MR 723569 (85d:05148) 14

    1983

  9. [17]

    , Graph minors—A survey, Surveys in combinatorics 1985 (Glasgow, 1985), London Math. Soc. Lecture Note Ser., vol. 103, Cambridge Univ. Press, Cambridge, 1985, pp. 153–171. MR 822774 (87e:05130)

    1985

  10. [18]

    , Graph minors. V. Excluding a planar graph , J. Combin. Theory Ser. B 41 (1986), no. 1, 92–114. MR 89m:05070 15

    1986

Pith tools

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