Separation profiles of free products
David Hume · 2026
Read Separation profiles of free products by David Hume (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-24462.txt.
Introduction
Hume uses a Dvorak-Norin theorem to show that separation profiles and treewidth profiles of graphs grow at the same rate, settling a question raised by Huang, Hume, Kelly, and Lam. He then applies the equivalence to Cayley graphs built from tree-graded graphs, expressing their separation profiles through the profiles of their pieces. Such tree-graded graphs cover the Cayley graphs arising from free products of finitely generated groups.
Catalog record
| CREATOR | David Hume |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 15208 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.24462
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Separation profiles of free products David Hume Abstract We deduce from a theorem of Dvorak–Norin that the separation and treewidth profiles of graphs are asymptotically equivalent, resolving a question of Huang–Hume–Kelly–Lam. As an application, we calculate the separation profiles of Cayley graphs of tree-graded graphs in terms of their pieces. Examples of tree-graded graphs include Cayley graphs of free products of finitely generated groups. 1 Introduction The separation profile, introduced by Benjamini–Schramm–Timár [ BST12 ] , assigns a sublinear function \sep_{X}:\mathbb{N}\to\mathbb{N} to each graph X=(VX,EX) that measures how robustly connected finite subgraphs of X are. For a full definition, see \lx@sectionsign\ref{defn:sep} . It satisfies a remarkable monotonicity property: given two bounded degree graphs X and Y , whenever there is a map \phi:VX\to VY and a constant \kappa such that \max_{xx^{\prime}\in EX}d_{Y}(\phi(x),\phi(x^{\prime}))\leq\kappa,\quad\textup{and}\quad\max_{y\in VY}|\phi^{-1}(y)|\leq\kappa (1.1) there is a constant C such that \sep_{X}(r)\leq C\sep_{Y}(Cr),\quad\forall r\in\mathbb{N}. (1.2) A map \phi:VX\to VY is said to be regular if it satisfies ( 1.1 ) for some \kappa . Examples of regular maps include: quasi-isometries, coarse embeddings and subgraph inclusions between bounded degree graphs. In particular, if X and Y are Cayley graphs of finitely generated groups H and G (with respect to any choice of finite generating sets), then there is a regular map VX\to VY whenever H is virtually (or even more generally, quasi-isometric to) a subgroup of G . Given functions f,g:\mathbb{N}\to\mathbb{N} we write f\lesssim g if there is a constant C such that f(r)\leq Cg(Cr)+C for all r\in\mathbb{N} and we write f\simeq g if f\lesssim g and g\lesssim f (so ( 1.2 ) states that \sep_{X}\lesssim\sep_{Y} ). We consider separation profiles as \simeq -equivalence classes of functions, meaning that a finitely generated group has a well-defined separation profile - that of any of its Cayley graphs. The separation profile is a powerful invariant in coarse geometry and its applications in group theory. Among finitely generated polycyclic groups it recognises those with polynomial growth of degree d (that satisfy \sep_{G}(r)\simeq r^{1-\frac{1}{d}} ) from those of exponential growth (that satisfy \sep_{G}(r)\simeq r/\log(r) ), and among Riemannian symmetric spaces, it recognises those whose noncompact factor has rank at most 1 from those with higher rank [ HMT20 , HMT22 ] . It is also connected with many other interesting invariants such as isoperimetry, growth and conformal dimension for compact metric spaces [ GC23 , GS21 , HM25 ] . A long-standing and slightly irritating gap in our understanding of separation profiles of groups concerns its behaviour under free products. We resolve this here. Theorem 1.3 . Let G and H be finitely generated groups. Then \sep_{G*H}(r)\simeq\max\{\sep_{G}(r),\sep_{H}(r)\} Using [ PW02 ] and standard arguments we deduce the following. Corollary 1.4 . Let G be the fundamental group of a finite graph of groups with finitely generated vertex groups \{G_{v}\} and finite edge groups. Then \sep_{G}(r)\simeq\max\{\sep_{G_{v}}(r)\} The proof of Theorem 1.3 has two steps. Firstly, we show how a theorem of Dvorak–Norin implies that the separation profile of any graph can be asymptotically determined by the treewidth (denoted \tw , cf. Definition 2.3 ) of its finite subgraphs. Proposition 1.5 . Let X=(VX,EX) be a graph. Then for every r , \sep_{X}(r)-1\leq\max\left\{\tw(\Gamma)\ \left|\ \Gamma\leq X,\ |V\Gamma|\leq r\right.\right\}\leq 15\sep_{X}(r) Treewidth was introduced by Robertson–Seymour as a measure of how tree-like a graph is [ RS86 ] . It is an important invariant in its own right and has many applications, see [ Bod06 ] and references therein. The function \tw_{X}(r)=\max\left\{\tw(\Gamma)\ \left|\ \Gamma\leq X,\ |V\Gamma|\leq r\right.\right\} is called the treewidth profile in [ HHKL26 ] . Proposition 1.5 resolves Question 4.1 from that paper. Secondly, we show that the treewidth of a tree-graded graph (a graph made of “pieces” arranged in a tree-like manner, cf. Definition 3.1 ) depends only on the treewidth of the pieces. Proposition 1.6 . Let X be a tree-graded graph with pieces (X_{i})_{i\in I} . Then \tw_{X}(r)=\max\left\{\tw_{X_{i}}(r)\ \left|\ i\in I\right.\right\}. The proof of Theorem 1.3 then proceeds as follows. Let S,T be finite generating sets of G and H respectively. Then S\sqcup T generates G*H and the Cayley graph X=\mathrm{Cay}(G*H,S\sqcup T) is tree-graded with pieces (X_{i})_{i\in I} where each X_{i} isomorphic to one of Y=\mathrm{Cay}(G,S) or Z=\mathrm{Cay}(H,T) . Now we apply Propositions 1.5 and 1.6 to deduce that \displaystyle\sep_{X}(r) \displaystyle\leq\tw_{X}(r)+1 \displaystyle\leq\max\{\tw_{Y}(r),\tw_{Z}(r)\}+1 \displaystyle\leq 15\max\{\sep_{Y}(r),\sep_{Z}(r)\}+1 As the separation profile of a finitely generated group does not depend (up to \simeq ) on the choice of generating set, we are done. Corollary 1.4 follows, as [ PW02 ] implies that any such G is quasi-isometric to a free product of some of the vertex groups with a (possibly trivial) finite rank free group, and the separation profile of a free group is bounded. We briefly mention immediate consequences for other invariants introduced in [ HHKL26 ] . In each case, they are defined by replacing treewidth in the definition of the treewidth profile by the mentioned graph layout parameter. Corollary 1.7 . Let G be the fundamental group of a finite graph of groups with finitely generated vertex groups \{G_{v}\} and finite edge groups. If G is not virtually cyclic, then the cutwidth profile of G is \cw_{G}(r)\simeq\max\{\sep_{G_{v}}(r),\log(1+r)\} the pathwidth profile of G is \pw_{G}(r)\simeq\max\{\sep_{G_{v}}(r),\log(1+r)\} and the sumcut profile of G is \sumcut_{G}(r)\simeq r\max\{\sep_{G_{v}}(r),\log(1+r)\} 2 Treewidth, separation and balanced separators Here we collect the necessary definitions for non-specialists and deduce Proposition 1.5 from [ DN14 , Theorem 1] . We start with the separation and treewidth profiles. Definition 2.1 . Let \Gamma=(V\Gamma,E\Gamma) be a finite graph. The cutsize of \Gamma is the minimum cardinality of a subset S\subseteq V\Gamma with the property that every connected component of \Gamma-S contains at most \frac{1}{2}|V\Gamma| vertices. Definition 2.2 ( [ BST12 ] ) . Let X=(VX,EX) be any graph and let \varepsilon\in(0,1) . The separation profile of X is the function \sep_{X}:\mathbb{N}\to\mathbb{N} given by \sep_{X}(r)=\max\left\{\cut(\Gamma)\ \left|\ \Gamma\leq X,\ |V\Gamma|\leq r\right.\right\} Definition 2.3 ( [ RS86 ] ) . A tree-decomposition of a graph \Gamma=(V\Gamma,E\Gamma) is a pair (T,\{X_{g}\}_{g\in VT}) , where T=(VT,ET) is a tree, each X_{g}\subseteq V\Gamma , and 1. \bigcup_{g\in VT}X_{g}=V\Gamma , 2. for every edge vw\in E\Gamma there is some g\in VT such that v,w\in X_{g} , 3. for each v\in V\Gamma , the full subgraph of T with vertex set \left\{g\in VT\ \left|\ v\in X_{g}\right.\right\} is connected. The width of a tree-decomposition (T,\{X_{g}\}_{g\in VT}) is \max_{g\in VT}|X_{g}|-1 , and the treewidth of \Gamma , \tw(\Gamma) is the minimum width of a tree-decomposition of \Gamma . The treewidth profile of a graph X is the function \tw_{X}:\mathbb{N}\to\mathbb{N} given by \tw_{X}(r)=\max\left\{\tw(\Gamma)\ \left|\ \Gamma\leq X,\ |V\Gamma|\leq r\right.\right\} Dvorak–Norin find an upper bound for the treewidth of any graph in terms of the size of the balanced separators of its subgraphs. Definition 2.4 . A balanced separator of a finite graph \Gamma is a pair of subsets A,B\subseteq V\Gamma satsifying |A\setminus B|,|B\setminus A|\leq\frac{2}{3}|V\Gamma| such that there is no edge connecting A\setminus B to B\setminus A . The size of a balanced separator is |A\cap B| . The separation number of \Gamma , \sn(\Gamma) is the smallest s such that every subgraph of \Gamma admits a balanced separator of size at most s . With all these definitions in place, we may prove Proposition 1.5 . Proposition 2.5 . Let