Fat minors cannot be thinned (by quasi-isometries) (2024)

\tkzSetUpPoint

[fill=black, size = 3pt]\tkzSetUpLine[color=black, line width=0.6pt]\tkzSetUpCircle[color=black, line width=0.6pt]

James Davies ¹¹1Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Cambridge, UK (jgd37@cam.ac.uk). Robert Hickingbotham ²²2School of Mathematics, Monash University, Melbourne, Australia (robert.hickingbotham@monash.edu). Research supported by an Australia Mathematical Society Lift-Off Fellowship and the Monash Postgraduate Publication Award.
Freddie Illingworth ³³3Department of Mathematics, University College London, London, UK (f.illingworth@ucl.ac.uk). Research supported by EPSRC grant EP/V521917/1 and the Heilbronn Institute for Mathematical Research. Rose McCarty ⁴⁴4School of Mathematics and School of Computer Science, Georgia Institute of Technology, Atlanta, USA (rmccarty3@gatech.edu). Supported by the National Science Foundation under Grant No.DMS-2202961.

Abstract

We disprove the conjecture of Georgakopoulos and Papasoglu that a length space (or graph) with no $K$ -fat $H$ minor is quasi-isometric to a graph with no $H$ minor. Our counterexample is furthermore not quasi-isometric to a graph with no 2-fat $H$ minor or a length space with no $H$ minor.On the other hand, we show that the following weakening holds: any graph with no $K$ -fat $H$ minor is quasi-isometric to a graph with no $3$ -fat $H$ minor.

1 Introduction

Inspired by connections to metric geometry, fat minors were independently introduced by Chepoi, Dragan, Newman, Rabinovich, and Vaxes[CDN+12] and Bonamy, Bousquet, Esperet, Groenland, Liu, Pirot, and Scott[BBE+23] as a coarse variant of graph minors.They have been a key tool in resolving open problems at the intersection of structural graph theory and coarse geometry [BBE+23].Georgakopoulos and Papasoglu[GP23] recently gave a systematic overview of this blossoming area which can be described as “coarse graph theory”.At the heart of their paper, they proposed a natural conjecture that would effectively lift graph minor theory to the coarse setting: for every finite graph $H$ , graphs with no fat $H$ minor are quasi-isometric to graphs with no $H$ minor. Quasi-isometry is a fundamental notion from geometric group theory which preserves the large-scale geometry of a metric space. So, if true, this conjecture would imply coarse analogues to various results from graph minor theory, such as the Graph Minor Structure Theorem of Robertson and Seymour[RS03].

Georgakopoulos and Papasoglu’s conjecture has been settled for particular graphs $H$ . Manning[Man05] characterised quasi-trees which implies the case $H=K_{\_}3$ (see[GP23]). The case $H=K_{\_}{2,3}$ was proved by Chepoi, Dragan, Newman, Rabinovich, and Vaxes[CDN+12], and more generally, Fujiwara and Papasoglu[FP23] recently characterised quasi-cacti. The case $H=K_{\_}{1,m}$ was recently settled by Georgakopoulos and Papasoglu[GP23].

Our main contribution is a counterexample to the conjecture of Georgakopoulos and Papasoglu.

Theorem 1.

There exists a finite graph $H$ such that, for every $q\in\mathbb{N}$ , there is a graph $G_{\_}q$ that does not contain $H$ as a $3$ -fat minor and is not $q$ -quasi-isometric to any graph with no ( $2$ -fat) $H$ minor.

In fact, Theorem1 gives a strong counterexample to Georgakopoulos and Papasoglu’s conjecture, since we can find $H$ as a 2-fat minor, rather than just as a minor.One might hope that an analogue of the conjecture might still hold for edge weighted graphs or, more generally, length spaces, but this is not the case.

Theorem 2.

It turns out that Theorem1 is essentially tight;we prove that graphs with no $K$ -fat $H$ minor are $K$ -quasi-isometric to graphs with no $3$ -fat $H$ minor.By scaling,Theorem2 is also similarly tight up to some positive factor depending on $q$ (see 10).

Theorem 3.

Let $K$ be a positive integer, $\mathcal{H}$ a non-empty collection of graphs, and $G$ a graph that has no $K$ -fat $H$ minor for every $H\in\mathcal{H}$ . Then $G$ is $K$ -quasi-isometric to a graph $\widehat{G}$ that does not contain a $3$ -fat $H$ minor for each $H\in\mathcal{H}$ .

2 Preliminaries

A length space is a metric space $(M,d)$ such that, for every $x,y\in M$ and $\varepsilon>0$ , there is an $(x,y)$ -arc of length at most $d(x,y)+\varepsilon$ whenever $d(x,y)$ is finite.In particular, every graph (where the edges are arcs of length one) is a length space (in which one can even take $\varepsilon=0$ ). Graphs with arbitrary non-negative real-valued edge-lengths also induce a length space. See [BH99] for further background on length spaces.

For point sets $X,Y$ in a length space $G$ , an $(X,Y)$ -path is a path in $G$ with one end-point in $X$ and the other in $Y$ . The distance between $X$ and $Y$ , denoted $\operatorname{dist}_{\_}G(X,Y)$ is the infimum of the lengths of the $(X,Y)$ -paths in $G$ . Note that this corresponds to the usual notion of distance for graphs.

We say that a set of points $Y$ in a length space $G$ is path-connected if, for every $x,y\in Y$ , there is an $(x,y)$ -path contained in $Y$ .Note that this corresponds to the usual notion of connectivity for graphs.For a length space $G$ , a non-negative real $r$ , and a set of points $Y$ , we let $N_{\_}G^{r}[Y]$ denote the set of points $a$ such that there is an $(a,Y)$ -path in $G$ of length at most $r$ . In graphs this is just the set of points at distance at most $r$ from $Y$ .Note that for any point $y\in G$ , $N_{\_}G^{r}[\{y\}]$ is always path-connected.

For a positive integer $K$ , a $K$ -fat minor model of a graph $H$ in a length space $G$ is a collection $(B_{\_}v\colon v\in V(H))\cup(P_{\_}e\colon e\in E(H))$ of path-connected sets in $G$ such that

•
$V(B_{\_}v)\cap V(P_{\_}e)\neq\varnothing$ whenever $v$ is an end of $e$ in $H$ ; and
•
for any pair of distinct $X,Y\in\{B_{\_}v\colon v\in V(H)\}\cup\{P_{\_}e\colon e\in E(H)\}$ not covered by the above condition, we have $\operatorname{dist}_{\_}G(X,Y)\geqslant K$ .

If $G$ contains an $K$ -fat minor model of $H$ , then we say that $H$ is a $K$ -fat minor of $G$ .

For $q\in\mathbb{N}$ , a $q$ -quasi-isometry of a length space $G$ into a length space $\widehat{G}$ is a map $\phi\colon X\to\widehat{X}$ such that, for every $x,y\in X$ ,

q^{-1}\cdot\operatorname{dist}_{\_}X(x,y)-q\leqslant\operatorname{dist}_{\_}{%\widehat{X}}(\phi(x),\phi(y))\leqslant q\cdot\operatorname{dist}_{\_}X(x,y)+q,

and, for every $\widehat{v}\in\widehat{X}$ , there is a $v\in X$ with $\operatorname{dist}_{\_}{\widehat{X}}(\widehat{v},\phi(v))\leqslant q$ . If $\widehat{X}$ is a graph, then we restrict to quasi-isometries $\phi$ with $\phi\colon X\to V(\widehat{X})$ .

Let $G$ be a graph and $Z\subseteq V(G)$ . We write $G[Z]$ for the subgraph of $G$ induced on $Z$ . We refer to $Z$ and $G[Z]$ interchangeably, whenever there is no chance of confusion. A graph $J$ is a subdivision of a $G$ if $J$ can be obtained from $G$ by replacing each edge $uv$ of $G$ by a path with end-vertices $u$ and $v$ . If each path has exactly $k$ internal vertices, then we say that $J$ is the $k$ -subdivision of $G$ .

For a graph $G$ , a tree-decomposition of $G$ is a collection of bags $(B_{\_}x\subseteq V(G)\colon x\in V(T))$ indexed by a tree $T$ such that for each $v\in V(G)$ , $T[\{x\in V(T)\colon v\in B_{\_}x\}]$ is a non-empty subtree of $T$ ; and for each $uv\in E(G)$ , there is a node $x\in V(T)$ such that $u,v\in B_{\_}x$ . The width of $(B_{\_}x\subseteq V(G)\colon x\in V(T))$ is $\max\{\lvert B_{\_}x\rvert-1\colon x\in V(T)\}$ . The treewidth $\operatorname{tw}(G)$ of a graph $G$ is the minimum width of a tree-decomposition of $G$ . Treewidth is a fundamental parameter in algorithmic and structural graph theory and is the standard measure of how similar a graph is to a tree.

3 Removing coarseness counterexample

3.1 The construction

We start with Nguyen, Scott, and Seymour’s counterexample to a conjectured coarse version of Menger’s theorem[NSS24]. For a positive integer $q$ , they defined the graph $N_{\_}q$ shown in Figure1 where the complete binary treehas depth $13q^{2}$ with each solid line being an edge and each dotted line represents a path of length $14q^{2}$ .

Fat minors cannot be thinned (by quasi-isometries) (1)

They proved that $N_{\_}q$ has the following property.

Lemma 4 ([NSS24]).

Let $S$ and $T$ be the sets of the three vertices in $N_{\_}q$ as shown in the figure,and let $P_{\_}1$ , $P_{\_}2$ , $P_{\_}3$ be three $(S,T)$ -paths in $N_{\_}q$ . Then there exist distinct $i,j\in\{1,2,3\}$ such that $\operatorname{dist}(P_{\_}i,P_{\_}j)\leqslant 2$ .

We prove an additional property of $N_{\_}q$ .

Lemma 5.

$N_{\_}q$ has treewidth at most seven.

Proof.

Subdividing an edge does not change the treewidth of a graph and so $N_{\_}q$ has the same treewidth as the graph $N^{\prime}_{\_}q$ where each dotted segment has been replaced by an edge. Contract the following edges of the path at the bottom of $N^{\prime}_{\_}q$ : the edges joining the 1st and 2nd vertices, 3rd and 4th vertices, the 5th and 6th vertices, …. The resulting graph $N^{\prime\prime}_{\_}q$ is a minor of the graph depicted in Figure2.

Fat minors cannot be thinned (by quasi-isometries) (2)

The graph in Figure2 is a subgraph of a Halin graph¹¹1A Halin graph is a planar graph that can be constructed from a planar embedding of a tree by connecting its leaves with a cycle which passes around the tree’s boundary. and so has treewidth at most three[Bod88]. Thus $\operatorname{tw}(N^{\prime\prime}_{\_}q)\leqslant 3$ . When contracting the edges to get from $N^{\prime}_{\_}q$ to $N^{\prime\prime}_{\_}q$ , the bags drop in size by a factor of at most two and so $\operatorname{tw}(N_{\_}q)=\operatorname{tw}(N^{\prime}_{\_}q)\leqslant 7$ , as required.∎

Now we turn to the construction of $H$ and $G_{\_}q$ in Theorem1.

Let $L$ and $R$ be vertex-disjoint copies of $K_{\_}{15}$ with vertex-sets $\{x_{\_}1,\dotsc,x_{\_}{15}\}$ and $\{y_{\_}1\dotsc,y_{\_}{15}\}$ , respectively. Let $H$ be the graph obtained from the union of $L$ and $R$ by adding the edges $x_{\_}1y_{\_}1$ , $x_{\_}2y_{\_}2$ , $x_{\_}3y_{\_}3$ as shown in Figure3.We will use the following properties of $H$ :

(i)
$L$ and $R$ are both $4$ -connected graphs with treewidth $14$ ; and
(ii)
$H$ and $(H\backslash\{x_{\_}2y_{\_}2,x_{\_}3y_{\_}3\})\cup\{x_{\_}2y_{\_}3,x_{\_}3y_{%\_}2\}$ are isomorphic.

The graph $G_{\_}q$ is obtained as follows and shown in Figure4.Let $L^{\star}$ be a $16q^{2}$ -subdivision of $K_{\_}{15}$ and let $R^{\star}$ be a $16q^{2}$ -subdivision of $K_{\_}{15}$ . We let $x_{\_}1^{\star},\dotsc,x_{\_}{15}^{\star}$ and $y_{\_}1^{\star},\dotsc,y_{\_}{15}^{\star}$ denote the high degree vertices of $L^{\star}$ and $R^{\star}$ , respectively.Take disjoint copies of each of $L^{\star}$ , $R^{\star}$ , and $N_{\_}q$ .Label the $S$ vertices of $N_{\_}q$ as $S_{\_}1$ , $S_{\_}2$ , $S_{\_}3$ and the $T$ vertices of $N_{\_}q$ as $T_{\_}1$ , $T_{\_}2$ , $T_{\_}3$ .For each $i\in\{1,2,3\}$ add a path of length $16q^{2}$ from $x_{\_}i^{\star}$ to $S_{\_}i$ and add a path of length $16q^{2}$ from $y_{\_}i^{\star}$ to $T_{\_}i$ .

3.2 Avoiding fat minors

We now show that $G_{\_}q$ does not contain $H$ as a 3-fat minor.

Lemma 6.

For every $q\in\mathbb{N}$ , $G_{\_}q$ does not contain $H$ as a $3$ -fat minor.

Proof.

Suppose that $G_{\_}q$ contains $H$ as a $3$ -fat minor. Let $(B_{\_}v\colon v\in V(H))$ and $(P_{\_}e\colon e\in E(H))$ be a $3$ -fat minor model of $H$ in $G_{\_}q$ . We begin by considering the $3$ -fat sub-model of $L$ in $G_{\_}q$ .

Claim 1:There exists $z\in V(L)$ such that $B_{\_}z\subseteq L^{\star}$ or $B_{\_}z\subseteq R^{\star}$ .

Proof.

Let $\tilde{N}_{\_}q=G_{\_}q-L^{\star}-R^{\star}$ . Since $\tilde{N_{\_}q}$ is obtained from $N_{\_}q$ by adding paths, each with one end-vertex on $N_{\_}q$ , it follows that $\operatorname{tw}(\tilde{N}_{\_}q)=\operatorname{tw}(N_{\_}q)$ . Now suppose that $V(B_{\_}v)\cap V(\tilde{N}_{\_}q)\neq\varnothing$ for every $v\in V(L)$ . Let $X=\{v\in V(L)\colon V(B_{\_}v)\not\subseteq V(\tilde{N}_{\_}q)\}$ and $Y=\{uv\in E(L-X)\colon V(P_{\_}{uv})\not\subseteq V(\tilde{N}_{\_}q)\}$ . Then $L-X-Y$ is a minor of $\tilde{N}_{\_}q$ .Since every path in $G_{\_}q$ from $V(\tilde{N}_{\_}q)$ to $V(L^{\star})\cup V(R^{\star})$ contains a vertex from $\{x_{\_}1^{\star},x_{\_}2^{\star},x_{\_}3^{\star},y_{\_}1^{\star},y_{\_}2^{%\star},y_{\_}3^{\star}\}$ , it follows that $|X\cup Y|\leqslant 6$ . Therefore $\operatorname{tw}(\tilde{N}_{\_}q)\geqslant\operatorname{tw}(L-X-Y)\geqslant%\operatorname{tw}(L)-6\geqslant 8$ , contradicting Lemma5. As such, there exists $z\in V(L)$ such that $V(B_{\_}z)\cap V(\tilde{N}_{\_}q)=\varnothing$ . Since $B_{\_}z$ is connected, it follows that either $B_{\_}z\subseteq L^{\star}$ or $B_{\_}z\subseteq R^{\star}$ .∎

By symmetry, we may assume without loss of generality that $B_{\_}z\subseteq L^{\star}$ .

Claim 2: For every $v\in V(L)$ , $V(B_{\_}v)\cap V(L^{\star})\neq\varnothing$ .

Proof.

Suppose there is some vertex $v\in V(L)$ such that $V(B_{\_}v)\cap V(L^{\star})=\varnothing$ . Then every $(B_{\_}z,B_{\_}v)$ -path in $G_{\_}q$ contains a vertex from $\{x_{\_}1^{\star},x_{\_}2^{\star},x_{\_}3^{\star}\}$ . So $G_{\_}q$ contains at most three vertex-disjoint $(B_{\_}z,B_{\_}v)$ -paths, which contradicts $(B_{\_}v\colon v\in V(L))$ and $(P_{\_}e\colon e\in E(L))$ being a $3$ -fat model of a $4$ -connected graph.∎

Claim 3: Every vertex of degree at least $3$ in $L^{\star}$ is contained in $B_{\_}v$ for some $v\in V(L)$ .

Proof.

Let $v\in V(L)$ . Since $\deg_{\_}L(v)\geqslant 3$ , $B_{\_}v$ contains a vertex in $G_{\_}q$ of degree at least $3$ . If $V(B_{\_}v)\subseteq V(L^{\star})$ , then $B_{\_}v$ contains a vertex of degree at least $3$ in $L^{\star}$ . If $V(B_{\_}v)\cap V(N_{\_}q)\neq\varnothing$ , then Claim 2 implies that $B_{\_}v$ contains $x_{\_}1^{\star}$ , $x_{\_}2^{\star}$ , or $x_{\_}3^{\star}$ . So each $B_{\_}v$ contain a vertex of degree at least $3$ in $L^{\star}$ . Since $\lvert\{u\in V(L^{\star})\colon\deg_{\_}{L^{\star}}(u)\geqslant 3\}\rvert=%\lvert V(L)\rvert$ , the claim then follows.∎

We now consider the $3$ -fat sub-model of $R$ in $G_{\_}q$ .

Claim 4: For every $u\in V(R)$ , $V(B_{\_}u)\cap V(R^{\star})\neq\varnothing$ .

Proof.

By symmetry, Claims 1 & 2 imply that either $V(B_{\_}u)\cap V(L^{\star})\neq\varnothing$ for every $u\in V(R)$ , or $V(B_{\_}u)\cap V(R^{\star})\neq\varnothing$ for every $u\in V(R)$ . Suppose that $V(B_{\_}u)\cap V(L^{\star})\neq\varnothing$ for every $u\in V(R)$ . Then there is a vertex $u\in V(R)$ such that $B_{\_}u\subseteq L^{\star}$ . Since $\deg_{\_}R(u)\geqslant 3$ , it follows that $B_{\_}u$ contains a vertex of degree at least $3$ from $L^{\star}$ . But by Claim 3, this implies that $V(B_{\_}u)\cap V(B_{\_}v)\neq\varnothing$ for some $v\in V(L)$ , a contradiction. Therefore, $V(B_{\_}u)\cap V(R^{\star})\neq\varnothing$ for every $u\in V(R)$ .∎

To conclude the proof, consider the edges $x_{\_}1y_{\_}1,x_{\_}2y_{\_}2,x_{\_}3y_{\_}3\in E(H)$ .For each $i\in\{1,2,3\}$ , let $P_{\_}i$ be the path in our model that corresponds to $x_{\_}iy_{\_}i$ . Since $B_{\_}{x_{\_}i}\cup P_{\_}i\cup B_{\_}{y_{\_}i}$ is connected, Claims 2 & 4 imply that there is an $(L^{\star},R^{\star})$ -path $P_{\_}i^{\prime}$ in $B_{\_}{x_{\_}i}\cup P_{\_}i\cup B_{\_}{y_{\_}i}$ . By Lemma4, there are distinct $i,j\in\{1,2,3\}$ such that $\operatorname{dist}_{\_}{G_{\_}q}(P_{\_}i^{\prime},P_{\_}j^{\prime})\leqslant 2$ . Therefore, there is $X_{\_}i\in\{B_{\_}{x_{\_}i},P_{\_}i,B_{\_}{y_{\_}i}\}$ and $X_{\_}j\in\{B_{\_}{x_{\_}j},P_{\_}j,B_{\_}{y_{\_}j}\}$ such that $\operatorname{dist}_{\_}{G_{\_}q}(X_{\_}i,X_{\_}j)\leqslant 2$ , contradicting $(B_{\_}v\colon v\in V(H))$ and $(P_{\_}e\colon e\in E(H))$ being $3$ -fat.∎

3.3 Finding fat minors

In this subsection, we shall find $H$ as a fat minor in length spaces (or graphs) that are quasi-isometric to $G_{\_}q$ .

Lemma 7.

Let $\widehat{G}$ be a length space that is $q$ -quasi-isometric to $G_{\_}q$ .If $\widehat{G}$ is a graph, then let $K=2$ , otherwise let $K=2^{-13q^{2}}$ .Then $\widehat{G}$ contains $H$ as a $K$ -fat minor.

Lemmas6 and7 immediately implies Theorems1 and2. Before proving Lemma7, we need the following two lemmas to help us build our fat $H$ model in $\widehat{G}$ . The first lemma allows us to find path-connected sets in $\widehat{G}$ which spans a set of elements, while the second lemma allows us to find path-connected sets in $\widehat{G}$ that are sufficiently far away from each other.

Fat minors cannot be thinned (by quasi-isometries) (2024)

Abstract

1 Introduction

Theorem 1.

Theorem 2.

Theorem 3.

2 Preliminaries

3 Removing coarseness counterexample

3.1 The construction

Lemma 4 ([NSS24]).

Lemma 5.

Proof.

3.2 Avoiding fat minors

Lemma 6.

Proof.

Proof.

Proof.

Proof.

Proof.

3.3 Finding fat minors

Lemma 7.

Lemma 8.