pith. sign in

arxiv: 2606.19473 · v1 · pith:LJVZS3LXnew · submitted 2026-06-17 · 🧮 math.CO

Vertex cuts and median decompositions

Joseph P. MacManus , Bobby Miraftab This is my paper

Pith reviewed 2026-06-26 20:02 UTC · model grok-4.3

classification 🧮 math.CO
keywords median decompositionsvertex separationsmedian graphsclique numbertree decompositionsSageev dualitygroup actionsCayley graphs
0
0 comments X

The pith

Any system of vertex separations in a graph yields a uniquely minimal median decomposition whose width equals the graph's clique number.

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

The paper shows how to build median decompositions from arbitrary, possibly non-nested, collections of vertex cuts by using Sageev's dual median graph as the underlying structure. When the cuts are nested the construction reduces exactly to a tree decomposition over the associated structure tree. The authors prove that every such median decomposition is uniquely minimal and then apply the result to prove that the median-width of an arbitrary graph equals its clique number. A further consequence is a characterization, for finitely generated groups, of when the group admits a metrically proper or geometric action on a median graph in terms of canonical median decompositions of its Cayley graphs.

Core claim

For every graph G and every (not necessarily nested) system of vertex separations, the dual median graph constructed by Sageev supplies a median decomposition of G that is uniquely minimal; when the system is nested the decomposition recovers the usual tree decomposition. As a direct consequence the median-width of G equals the size of its largest clique, and this holds for infinite graphs as well as finite ones. The same structural facts yield a characterization of metrically proper and geometric actions of finitely generated groups on median graphs via canonical median decompositions of their Cayley graphs.

What carries the argument

Sageev's dual median graph built from a system of vertex separations, which becomes the structure graph of the resulting median decomposition and carries the uniqueness and width properties.

If this is right

  • Non-nested systems of vertex separations produce median decompositions that properly generalize ordinary tree decompositions.
  • When the system of separations is nested the median decomposition coincides exactly with the tree decomposition over the structure tree.
  • The median-width of every graph equals its clique number.
  • A finitely generated group admits a metrically proper or geometric action on a median graph precisely when the canonical median decompositions of its Cayley graphs satisfy the corresponding width and equivariance conditions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The uniform treatment of finite and infinite graphs suggests that algorithmic or structural questions about clique number in infinite graphs might be approachable through median-width computations.
  • The explicit link between canonical median decompositions and group actions on median graphs may supply new quasi-isometry invariants for finitely generated groups.
  • Sageev-Roller duality, now visible inside median decompositions, could be used to translate separation questions in graphs into questions about median graphs and vice versa.

Load-bearing premise

The dual median graph obtained from an arbitrary system of vertex separations is always well-defined and produces a median decomposition that satisfies the claimed uniqueness and width properties for every graph, finite or infinite.

What would settle it

An explicit graph (finite or infinite) together with a system of vertex separations whose Sageev dual fails to give a median decomposition of width equal to the clique number, or fails to be uniquely minimal.

Figures

Figures reproduced from arXiv: 2606.19473 by Bobby Miraftab, Joseph P. MacManus.

Figure 2
Figure 2. Figure 2: The median-decomposition of P4 This motivates the following definition. Definition 4.12. Let G be a graph and (M, β) be a median decomposition. Then (M, β) is said to be crossing-faithful if, for all pairs h, h ′ ∈ H⃗ (M) of crossing Θ￾classes, we have that the induced separations (Ah, Bh) and (Ah′ , Bh′ ) also cross. We will see in Section 6.3 that a reduced, crossing-faithful median decomposition is comp… view at source ↗
Figure 6
Figure 6. Figure 6: The triangle-augmented cuboctahedral graph. 7. Stavropoulos’ characterisation of clique number In this section apply our machinery for constructing median decompositions, and extend a theorem of Stavropoulos. In [33], Stavropoulos shows that the median￾width of a finite graph is exactly its clique number. The goal of this section is to [PITH_FULL_IMAGE:figures/full_fig_p025_6.png] view at source ↗
read the original abstract

Median decompositions were introduced by Stavropoulos in 2015 as a generalisation of tree decompositions. In this paper, we further develop and exposit this theory as a tool in structural graph theory to study systems of vertex separations. Generalising the well-known fact that nested systems of vertex separations produce tree decompositions of a graph over the structure tree, we describe how a (not necessarily nested) system of separations produces a median decomposition. The median graph in this decomposition is the `dual median graph' constructed by Sageev. If the system of cuts is nested then this median decomposition recovers precisely the aforementioned tree decomposition. We prove a theorem asserting that this decomposition is `uniquely minimal', and describe how Sageev--Roller duality manifests in median decompositions. As an application of our structural approach, we extend a theorem of Stavropoulos from finite graphs to all graphs, which states that the median-width a graph is equal to its clique number. We also describe the link between (canonical) median decompositions and (equivariant) coarse embeddings/quasi-isometries into median graphs. A corollary of these results is a characterisation of when a finitely generated group acts metrically-properly/geometrically on a median graph, in terms of canonical median decompositions of its Cayley graphs.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper develops the theory of median decompositions of graphs induced by arbitrary (not necessarily nested) systems of vertex separations. It shows that any such system yields a median decomposition whose underlying median graph is the dual median graph constructed by Sageev; when the system is nested this recovers the standard tree decomposition over the structure tree. The authors prove that the resulting decomposition is uniquely minimal and describe the manifestation of Sageev–Roller duality in this setting. The central application extends Stavropoulos’ theorem from finite graphs to all graphs by proving that the median-width of G equals ω(G). A further corollary characterises when a finitely generated group admits a metrically proper or geometric action on a median graph in terms of canonical median decompositions of its Cayley graphs.

Significance. If the extension to infinite graphs is correct, the work supplies a canonical structural tool for studying vertex-separation systems in both finite and infinite graphs and yields a clean characterisation in geometric group theory. The explicit use of Sageev’s dual construction and the recovery of tree decompositions as a special case are strengths; the paper also supplies reproducible constructions rather than parameter-dependent fits.

major comments (2)
  1. [Theorem extending Stavropoulos (median-width = ω(G))] The proof that the Sageev dual median graph produces a median decomposition of width exactly ω(G) for arbitrary (possibly infinite) separation systems is load-bearing for the main theorem. The manuscript must explicitly verify that the Helly property for medians, the width calculation, and the uniqueness of the minimal decomposition hold without any implicit finiteness assumption on the graph or the separation system (e.g., no appeal to finite maximal cliques or finite branching).
  2. [Proof of unique minimality] The claim of unique minimality for the median decomposition obtained from a non-nested system should be checked against the possibility that, in infinite graphs, multiple non-isomorphic minimal median graphs could arise from the same separation system; the argument must rule this out directly rather than by reduction to the finite case.
minor comments (2)
  1. [Section introducing Sageev dual construction] Notation for the dual median graph and the associated decomposition should be introduced with a single consistent symbol rather than switching between descriptive phrases.
  2. [Corollary on group actions] The statement of the group-action corollary would benefit from an explicit reference to the precise notion of “canonical” median decomposition used.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their thorough review and for highlighting the need to ensure all arguments are fully explicit in the infinite setting. We address each major comment below. Where revisions are required to strengthen the exposition, we will incorporate them in the next version of the manuscript.

read point-by-point responses

  1. Referee: [Theorem extending Stavropoulos (median-width = ω(G))] The proof that the Sageev dual median graph produces a median decomposition of width exactly ω(G) for arbitrary (possibly infinite) separation systems is load-bearing for the main theorem. The manuscript must explicitly verify that the Helly property for medians, the width calculation, and the uniqueness of the minimal decomposition hold without any implicit finiteness assumption on the graph or the separation system (e.g., no appeal to finite maximal cliques or finite branching).

    Authors: We agree that explicit verification strengthens the extension to arbitrary graphs. The arguments in Sections 3–5 are written for general graphs and separation systems; they invoke only the intrinsic properties of median graphs (Helly property for intervals, convexity of bags) and the universal property of the Sageev dual, none of which invoke finiteness, finite branching, or finite maximal cliques. The width equals ω(G) because every bag is a clique and every maximal clique appears in some bag. Nevertheless, to address the referee’s request directly, we will insert a short paragraph immediately after the statement of the main theorem confirming that no finiteness hypothesis is used at any step. revision: yes

  2. Referee: [Proof of unique minimality] The claim of unique minimality for the median decomposition obtained from a non-nested system should be checked against the possibility that, in infinite graphs, multiple non-isomorphic minimal median graphs could arise from the same separation system; the argument must rule this out directly rather than by reduction to the finite case.

    Authors: The proof of unique minimality (Theorem 4.5) proceeds directly from the universal property of the Sageev dual: any median graph admitting the given separation system factors uniquely through the dual. This argument is formulated in the language of arbitrary (possibly infinite) median graphs and does not reduce to the finite case or appeal to finite branching. We will add an explicit sentence in the proof noting that the same reasoning applies verbatim when the underlying graph or the separation system is infinite, thereby ruling out the possibility of distinct minimal models. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivations rest on explicit constructions from separations and Sageev's independent prior work.

full rationale

The paper defines median decompositions via systems of vertex separations, with the median graph taken directly as Sageev's dual construction (a pre-existing external result). The extension of Stavropoulos' finite-graph theorem to all graphs proceeds by proving the decomposition is uniquely minimal and has width equal to the clique number, using the same construction without any reduction of the target equality to a fitted parameter, self-definition, or self-citation chain. The uniqueness claim is asserted as a theorem proved in this paper. No equations or steps reduce the claimed results to their inputs by construction. This is the normal case of a self-contained structural argument against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on the prior definitions of median decompositions (Stavropoulos 2015) and Sageev's dual median graph; no new free parameters, ad-hoc axioms, or invented entities are introduced in the abstract.

axioms (1)
  • standard math Standard axioms and definitions of undirected graphs, vertex separations, tree decompositions, and median graphs as given in the cited literature.
    The abstract explicitly builds on Stavropoulos' 2015 introduction of median decompositions and Sageev's dual construction.

pith-pipeline@v0.9.1-grok · 5758 in / 1490 out tokens · 48540 ms · 2026-06-26T20:02:47.069459+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

34 extracted references · 11 canonical work pages

  1. [1]

    Connectivity and tree structure in finite graphs.Combinatorica, 34(1):11–45, 2014.doi:10.1007/s00493-014-2898-5

    Johannes Carmesin, Reinhard Diestel, Fabian Hundertmark, and Maya Stein. Connectivity and tree structure in finite graphs.Combinatorica, 34(1):11–45, 2014.doi:10.1007/s00493-014-2898-5

    work page doi:10.1007/s00493-014-2898-5 2014

  2. [2]

    Canonical trees of tree-decompositions.J

    Johannes Carmesin, Matthias Hamann, and Babak Miraftab. Canonical trees of tree-decompositions.J. Combin. Theory Ser. B, 152:1–26, 2022.doi:10. 1016/j.jctb.2021.08.004

    2022

  3. [3]

    Graphs of bounded chordality.Electron

    Aristotelis Chaniotis, Babak Miraftab, and Sophie Spirkl. Graphs of bounded chordality.Electron. J. Combin., 32(4):Paper No. 4.7, 22, 2025.doi:10. 37236/12956

    2025

  4. [4]

    From wall spaces toCAT(0)cube com- plexes.Internat

    Indira Chatterji and Graham Niblo. From wall spaces toCAT(0)cube com- plexes.Internat. J. Algebra Comput., 15(5-6):875–885, 2005.doi:10.1142/ S0218196705002669

    2005

  5. [5]

    Graphs of someCAT(0)complexes.Adv

    Victor Chepoi. Graphs of someCAT(0)complexes.Adv. in Appl. Math., 24(2):125–179, 2000.doi:10.1006/aama.1999.0677

    work page doi:10.1006/aama.1999.0677 2000

  6. [6]

    Zooming in on the large-scale geometry of locally compact groups

    Yves Cornulier and Pierre de la Harpe. Zooming in on the large-scale geometry of locally compact groups. 41:3–22, 2018

    2018

  7. [7]

    Graph Minors

    Reinhard Diestel.Graph theory, volume 173 ofGraduate Texts in Mathematics. Springer, Berlin, fifth edition, 2018.doi:10.1007/978-3-662-53622-3_12

    work page doi:10.1007/978-3-662-53622-3_12 2018

  8. [8]

    An alternative characterisation of graphs quasi-isometric to graphs of bounded treewidth.arXiv preprint arXiv:2512.21946, 2025

    Marc Distel. An alternative characterisation of graphs quasi-isometric to graphs of bounded treewidth.arXiv preprint arXiv:2512.21946, 2025

    arXiv 2025

  9. [9]

    Trees of tangles in infinite separation systems.Math

    Christian Elbracht, Jakob Kneip, and Maximilian Teegen. Trees of tangles in infinite separation systems.Math. Proc. Cambridge Philos. Soc., 173(2):297– 327, 2022.doi:10.1017/S0305004121000530

    work page doi:10.1017/s0305004121000530 2022

  10. [10]

    No quasi-isometric rigid- ity for proper actions onCAT(0)cube complexes.Proc

    Francesco Fournier-Facio and Anthony Genevois. No quasi-isometric rigid- ity for proper actions onCAT(0)cube complexes.Proc. Amer. Math. Soc., 151(12):5097–5109, 2023.doi:10.1090/proc/16544

    work page doi:10.1090/proc/16544 2023

  11. [11]

    Coning-offCAT(0)cube complexes

    Anthony Genevois. Coning-offCAT(0)cube complexes. volume 71, pages 1535–1599. 2021.doi:10.5802/aif.3430

    work page doi:10.5802/aif.3430 2021

  12. [12]

    Fixed-point-free actions on cubings.Siberian Advances in Math- ematics, 8(3):36–58, 1998

    V Gerasimov. Fixed-point-free actions on cubings.Siberian Advances in Math- ematics, 8(3):36–58, 1998

    1998

  13. [13]

    Isometries ofCAT(0)cube complexes are semi-simple.Ann

    Frédéric Haglund. Isometries ofCAT(0)cube complexes are semi-simple.Ann. Math. Qué., 47(2):249–261, 2023.doi:10.1007/s40316-021-00186-2

    work page doi:10.1007/s40316-021-00186-2 2023

  14. [14]

    A combination theorem for special cube complexes.Annals of mathematics, pages 1427–1482, 2012

    Frédéric Haglund and Daniel T Wise. A combination theorem for special cube complexes.Annals of mathematics, pages 1427–1482, 2012

    2012

  15. [15]

    Geom., 8(1-2):171–186, 1976.doi: 10.1007/BF01917434

    Rudolf Halin.S-functions for graphs.J. Geom., 8(1-2):171–186, 1976.doi: 10.1007/BF01917434

    work page doi:10.1007/bf01917434 1976

  16. [16]

    CRC press Boca Raton, 2011

    Richard H Hammack, Wilfried Imrich, Sandi Klavžar, Wilfried Imrich, and Sandi Klavžar.Handbook of product graphs, volume 2. CRC press Boca Raton, 2011. VERTEX CUTS AND MEDIAN DECOMPOSITIONS 35

    2011

  17. [17]

    Graphs quasi-isometric to graphs with bounded treewidth.arXiv preprint arXiv:2501.10840, 2025

    Robert Hickingbotham. Graphs quasi-isometric to graphs with bounded treewidth.arXiv preprint arXiv:2501.10840, 2025

    arXiv 2025

  18. [18]

    Finiteness properties of cubulated groups.Compositio Mathematica, 150(3):453–506, 2014

    G Christopher Hruska and Daniel T Wise. Finiteness properties of cubulated groups.Compositio Mathematica, 150(3):453–506, 2014

    2014

  19. [19]

    Cubulating graphs of free groups with cyclic edge groups.American journal of mathematics, 132(5):1153–1188, 2010

    Tim Hsu and Daniel T Wise. Cubulating graphs of free groups with cyclic edge groups.American journal of mathematics, 132(5):1153–1188, 2010

    2010

  20. [20]

    Canonicaltree-decompositionsofchordal graphs.arXiv preprint arXiv:2512.18480, 2025

    RaphaelWJacobsandPaulKnappe. Canonicaltree-decompositionsofchordal graphs.arXiv preprint arXiv:2512.18480, 2025

    Pith/arXiv arXiv 2025

  21. [21]

    Coarse embeddings into products of trees.Kyoto Journal of Mathematics, 62(1):225–229, 2022

    Daniel Kasprowski. Coarse embeddings into products of trees.Kyoto Journal of Mathematics, 62(1):225–229, 2022

    2022

  22. [22]

    Paul Knappe.Graph-decompositions: Trees, tangles and locality. Ph.D. thesis, Staats-und Universitätsbibliothek Hamburg Carl von Ossietzky, 2025

    2025

  23. [23]

    Logical aspects of cayley-graphs: the group case.Annals of Pure and Applied Logic, 131(1-3):263–286, 2005

    Dietrich Kuske and Markus Lohrey. Logical aspects of cayley-graphs: the group case.Annals of Pure and Applied Logic, 131(1-3):263–286, 2005

    2005

  24. [24]

    Coarse tree-width.arXiv preprint arXiv:2501.09839, 2025

    Tung Nguyen, Alex Scott, and Paul Seymour. Coarse tree-width.arXiv preprint arXiv:2501.09839, 2025

    arXiv 2025

  25. [25]

    Cubulating spaces with walls.Algebraic & Geometric Topology, 4(1):297–309, 2004

    Bogdan Nica. Cubulating spaces with walls.Algebraic & Geometric Topology, 4(1):297–309, 2004

    2004

  26. [26]

    Harry Petyt.On the large-scale geometry of mapping class groups. Ph.D. thesis, University of Bristol, 2022

    2022

  27. [27]

    Roller.Poc sets, median algebras and group actions

    Martin A. Roller.Poc sets, median algebras and group actions. Ph.D. thesis, University of Southampton, 1993

    1993

  28. [28]

    Ends of group pairs and non-positively curved cube com- plexes.Proc

    Michah Sageev. Ends of group pairs and non-positively curved cube com- plexes.Proc. London Math. Soc. (3), 71(3):585–617, 1995.doi:10.1112/ plms/s3-71.3.585

    1995

  29. [29]

    Codimension-1subgroups and splittings of groups.J

    Michah Sageev. Codimension-1subgroups and splittings of groups.J. Algebra, 189(2):377–389, 1997.doi:10.1006/jabr.1996.6884

    work page doi:10.1006/jabr.1996.6884 1997

  30. [30]

    Springer-Verlag, Hei- delberg, 2023, pp

    Petra Schwer.CAT(0)cube complexes—an introduction. 2324:xii+186, 2023. doi:10.1007/978-3-031-43622-2

    work page doi:10.1007/978-3-031-43622-2 2023

  31. [31]

    Cops, robber and medianwidth parameters.arXiv preprint arXiv:1603.06871, 2016

    Konstantinos Stavropoulos. Cops, robber and medianwidth parameters.arXiv preprint arXiv:1603.06871, 2016

    Pith/arXiv arXiv 2016

  32. [32]

    Konstantinos Stavropoulos.On Graph Sparsity and Structure: Colourings and Graph Decompositions. Ph.D. thesis, RWTH Aachen University, 2016

    2016

  33. [33]

    Stavropoulos

    Konstantinos S. Stavropoulos. On the medianwidth of graphs.CoRR, abs/1512.01104, 2015.1512.01104

    Pith/arXiv arXiv 2015

  34. [34]

    Finite asymptotic dimension forCAT(0)cube complexes.Geom

    Nick Wright. Finite asymptotic dimension forCAT(0)cube complexes.Geom. Topol., 16(1):527–554, 2012.doi:10.2140/gt.2012.16.527

    work page doi:10.2140/gt.2012.16.527 2012