# Bottlenecking In Graphs and a Coarse Menger-Type Theorem

Michael Bruner  University of Montana, 32 Campus Drive Missoula, MT 59812
<EMAIL_ADDRESS>,  Atish Mitra  Montana Technological University, 1300
West Park Street Butte, MT 59701<EMAIL_ADDRESS>and  Heidi Steiger  Montana
Technological University, 1300 West Park Street Butte, MT 59701
<EMAIL_ADDRESS>
###### Abstract.

We expand upon the notion of bottlenecking introduced in [7], characterizing a
spectrum of graphs and showing that this naturally extends to a concept of
coarse bottlenecking. We examine how bottlenecking differs from other notions
of connectedness. We show how the notion of bottlenecking provides a different
approach to coarsening measures of connectedness than the Coarse Menger
Conjecture proposed independently by Georgakopoulos and Papasoglu [9] as well
as Albrechtsen, Huynh, Jacobs, Knappe, and Wollan [4], which was recently
disproved by a counterexample [11]. We give a proof of a coarse Menger-type
theorem for the class of coarsely bottlenecked graphs, and provide a
conjecture that would extend this to all graphs.

###### Key words and phrases:

graph theory, coarse geometry, bottlenecking, coarse bottlenecking, graph
minor, coarse skeleton, Menger’s Theorem

###### 2020 Mathematics Subject Classification:

51F30, 05C10

The authors would like to thank Calvin University for their hospitality during
the Workshop in Geometric Topology 2024, where part of this manuscript was
completed.

##  1\. Introduction

Some special classes of edge bottlenecked graphs have been studied extensively
in classical graph theory. For example, graphs that are $1$-edge bottlenecked
are trees, and cacti are those that are $2$-edge bottlenecked. If one examines
these closer, there is a pattern where a cactus is a tree with some edges
added in to make cycles. A natural extension of this pattern gives
$3$-bottlenecked graphs as cacti with a few edges (or ”cuts”) added across the
cycles. We will call such a graph a cut-cactus.

Figure 1.  Examples of a tree, a cactus, and a cut-cactus. Each is produced
from the last by the addition of a few edges. Note that while each of these
graphs has a different bottlenecking number they are all 1-edge connected

More recently the coarse versions of these classes have proven to be of
interest in coarse graph theory [1, 2, 4].

In Section 3 we examine the differences between bottlenecking in graphs and
other notions of connectedness. In Section 4 we share a geometric, and a
excluded-minor characterization for 1,2 and 3 bottlenecked graphs. We also
give a excluded-minor characterization for $n$-bottlenecked graphs.

Menger’s theorem is a well known classical result in graph theory. Some
characterizations of bottlenecking follow as a natural result from Menger’s
Theorem [3]. A coarse version of Menger’s theorem was proposed by
Georgakopoulos and Papasoglu [9] as well as Albrechtsen, Huynh, Jacobs,
Knappe, and Wollan [4]. Subsequently in [11] an example was given to show that
this conjecture does not hold in the general case. In Section 5 we show how
the notion of bottlenecking naturally coarsens. Towards a characterization of
coarsely bottlenecked graphs we provide a coarse Menger-type theorem, then
propose a conjecture that - if true - extends this characterization to all
graphs. We also propose a conjecture about coarse bottlenecking similar in
spirit to [9] Conjecture 1.1, and show that - if our coarse Menger-type
conjecture holds - this conjecture is equivalent to a special case of [9]
Conjecture 1.1.

##  2\. Preliminaries

In this work we consider only connected, infinite and unbounded graphs. In
this section we reproduce definitions for many common notions from graph
theory and coarse geometry, for more information one may refer to a standard
text [5, 6].

######  Definition 2.1.

(Graph, Path, Cycle, $D_{n}$, Tree, Cactus, Cut-cactus) A graph $G$ is defined
to be two sets, a collections of vertices $V(G)$, and a collection of edges
$E(G)$. Each edge is associated with two vertices, said to be its endpoints. A
path is an ordered collection edges that join a set of distinct vertices, a
path between two sets of vertices $X$ and $Y$ is said to be an $X,Y$ path. A
cycle is a pair of paths that share exactly their endpoints. We often may
refer to trees, cactus and cut-cactus these are classes of graphs with
restrictions on the interactions of cycles. Trees have no cycles, cactus allow
cycles to only intersect at a single vertex, and cut-cactus allow cycles to
only intersect along a path. We often refer to a dipole graph $D_{n}$, this is
two vertices joined by $n$ edges.

######  Definition 2.2.

($n$-edge bottlenecking)(See [7]) A graph $G$ is said to have $n$-edge
bottlenecking if for any two disjoint connected sets $X,Y\subset V(G)$, there
exists a set $S\subseteq E(G)$ of size $n$ such that any $X,Y$ path contains
an element of $S$.

######  Definition 2.3.

($M$-fat/Coarse $n$-bottlenecking)(See [7]) A graph $G$ is said to have
$M$-fat $n$-bottlenecking for some $M,n\in\mathbb{N}$ if for any two
connected, $M$-disjoint subgraphs $X,Y\subset G$, there exists a set $S\subset
V(G)\setminus(V(X)\cup V(Y))$ of size $n$ such that every $X,Y$ path
intersects $N_{M}(S):=\\{x\in V(G)|d(x,S)<M\\}$. If a graph is $M$-fat
$n$-bottlenecked for some $M$ it is said to be coarsely $n$-bottlenecked. If
there exists an $n$ such that a graph is coarsely $n$-bottlenecked, the graph
is said to be coarsely bottlenecked.

######  Remark 2.1.

Bottlenecking defines a natural spectrum of graphs as $n$-edge bottlenecking
implies $(n+1)$-edge bottlenecking. This is also true for coarse
bottlenecking.

######  Definition 2.4.

(n-ladder/$M$-fat ladder) A graph is said to contain a $n$-ladder if there
exist disjoint connected sets $X$ and $Y$ such that there are $n$ $X,Y$ paths
that are disjoint outside of $X$ and $Y$. The sets $X$ and $Y$ are referred to
as the poles, and the paths are referred to as the rungs of the ladder. If the
poles are at least $M$-disjoint and the rungs are all pairwise $M$-disjoint a
ladder is said to be a $M$-fat ladder.

######  Remark 2.2.

A graph is $n$-edge bottlenecked iff it contains no $(n+1)$-ladders.

This result follows from Menger’s Theorem (see Remark 3.5).

######  Definition 2.5.

(Minor, $M$-fat/Asymptotic Minor) (See [9, 12]) A graph $G$ is said to contain
a graph $H$ as a minor if there exist a subgraph of $G$ that is the union of
disjoint sets corresponding to each of the vertices and edges of $H$, such
that contracting each set produces the graph $H$. If these sets are
$M$-disjoint except where they are incident in $H$ then this minor is said to
be a $M$-fat minor. If a graph contains a $M$-fat $H$ minor for any
$M\in\mathbb{N}$ then that graph is said to contain $H$ as an asymptotic
minor.

######  Remark 2.3.

A $n$-ladder is a $D_{n}$ minor, a $M$-fat $n$-ladder is a $M$-fat $D_{n}$
minor.

##  3\. Other Measures of Connectedness

######  Remark 3.1.

Bottlenecking is closely related to an existing and well understood notion
“Connectivity”. Informally bottlenecking measures how connected a graph is by
finding the area with the highest number of paths between two sets. Whereas
“Connectivity” measures how connected a graph is by finding the two points
with the fewest number of paths between them.

######  Definition 3.1 ($n$-Edge Connectivity).

A graph $G$ is said to have $n$-edge connectivity iff for any two vertices
$x,y\in V(G)$ there exists a set of at least $n$ $x,y$ paths that share no
edges.

######  Proposition 3.1.

If a graph is $n$-edge connected then it is not $(n-1)$-edge bottlenecked.

###### Proof.

If a graph is $n$-edge connected then any two vertices have at least $n$ edge
disjoint paths between them so there is a pair of two vertices $x,y$ such that
no set of $n-1$ edges intersects every $x,y$ path. ∎

######  Remark 3.2.

The converse of Proposition 3.1 does not hold showing that connectivity is a
stronger property than bottlenecking (see Figure 1).

######  Remark 3.3.

Similarly to edge bottlenecking and edge connectivity there exist notions of
point bottlenecking and point connectivity.

######  Definition 3.2.

($n$-point bottlenecking) A graph $G$ is said to have $n$-point bottlenecking
if for any two disjoint connected sets $X,Y\subset V(G)$, there exists a set
$S\subseteq V(G)$ of size $n$ such that any $X,Y$ path contains an element of
$S$.

######  Definition 3.3 ($n$-point Connectivity).

A graph $G$ is said to have $n$-point connectivity iff for any two vertices
$x,y\in V(G)$ there exists a set of at least $n$ internally disjoint $x,y$
paths.

######  Proposition 3.2.

If a graph is quasi-isometric to a $n$-edge bottlenecked graph then it is
quasi-isometric to a $n$-point bottlenecked graph.

###### Proof.

If a graph is $n$-edge bottlenecked then by subdividing every edge once a
graph with $n$-point bottlenecking may be produced. ∎

######  Remark 3.4.

It is not clear if there are $n$-point bottlenecked graphs that are not quasi-
isometric to a edge bottlenecked graph.

######  Remark 3.5 (Menger’s Theorem).

The edge (or vertex) connectivity of a graph is equal to the minimum number of
edges (or vertices) that must be removed from a graph to disconnect a graph.
This result is known as Menger’s Theorem. A coarse version of this was
recently conjectured by two sets of authors [9, 12] and a counterexample was
found [11] using a construction based around a large binary tree.

##  4\. Characterizations of $n$-edge bottlenecked graphs

######  Remark 4.1.

The class of connected graphs that are $1$-edge bottlenecked has been studied
extensively under the title ”Trees” and has proven to be of interest in many
different fields, a characterization simmilar to what one might find in any
textbook on graph theory is given here.

###  4.1. Trees

######  Proposition 4.1.

The following are equivalent

  1. (1)

A graph is $1$-edge bottlenecked.

  2. (2)

A graph does not contain $D_{2}$ as a minor.

  3. (3)

A graph has a unique path between any two vertices.

  4. (4)

A graph contains no cycles.

######  $1\implies 2$.

Assume to a contradiction a graph contains a $D_{2}$ minor, then the sets that
contract to form the vertices of $D_{2}$ give sets $X$ and $Y$ such that there
is no edge intersecting every $X,Y$ path, contradicting condition $1$. ∎

######  $2\implies 3$.

Assume to a contradiction that there were two distinct paths between two
vertices, then there is an edge in one path but not the other, by contracting
the whole graph to the endpoints of this edge a $D_{2}$ minor is produced,
contradicting condition $2$. ∎

######  $3\implies 4$.

If a graph has a unique path between any two vertices then there is no pair of
internally disjoint paths that share their endpoints. ∎

######  $4\implies 1$.

Assume to a contradiction that a graph is not $1$-edge bottlenecked, this
gives that there are connected sets $X$ and $Y$ such that there is no edge
that intersects every $X,Y$ path. There must be at least two $X,Y$ paths, and
there must be at least one edge contained in only one of these two paths. This
edge is a path between its endpoints, and as there is an $X,Y$ path not
through this edge there must be a second path between its endpoints, this
gives a cycle and contradicts condition $4$. ∎

###  4.2. Cacti

######  Remark 4.2.

The class of graphs that are $2$-edge bottlenecked is known to many as
”Cactus” graphs. These have been studied to some extent as well, but not to
the same level as trees.

######  Proposition 4.2.

The following are equivalent

  1. (1)

A graph is $2$-edge bottlenecked.

  2. (2)

A graph does not contain $D_{3}$ as a minor.

  3. (3)

The intersection of any two distinct cycles is at most a single vertex.

######  $1\implies 2$.

If a graph contains a $D_{3}$ minor then each of the sets that contract to
form the edges of $D_{3}$ give 3 disjoint paths between the sets that contract
to form the vertices of $D_{3}$. ∎

######  $2\implies 3$.

If the intersection of two cycles contains more than one vertex then it either
contains an edge or is disconnected. If the intersection is disconnected then
Proposition 4.4 gives a stronger result so we may assume towards a
contradiction there are two cycles with an intersection that is connected and
contains at least two vertices. By contracting the endpoints of this connected
region (that contains at least one edge) a $D_{3}$ minor is produced,
contradicting condition $2$. ∎

######  $3\implies 1$.

Assume to a contradiction that there are connected sets $X$ and $Y$ such that
no two edges will intersect every $X,Y$ path. This gives at least three edges
with three $X,Y$ paths such that each path uses only one of the edges. As $X$
and $Y$ are connected any pair of these paths gives a cycle, so two pairs of
paths give two cycles that share an edge. ∎

######  Proposition 4.3.

If a graph $G$ contains a $D_{3}$ minor then it contains a subdivision of
$D_{3}$.

###### Proof.

By Proposition 4.2 a $D_{3}$ minor implies there are two distinct cycles that
intersect at more than one vertex. let $C_{1}$ and $C_{2}$ be two such cycles.
Cycle $C_{1}$ contains a path $S$ with only its endpoints in $C_{2}$. $S\cup
C_{2}$ is a structure that can be produced by subdividing $D_{3}$. ∎

###  4.3. Cut-Cacti

######  Remark 4.3.

After trees and cactus, the class of three edge bottlenecked graphs we call
cut-cactus. The authors are, at the time of writing, unaware of any in-depth
study of such graphs.

######  Proposition 4.4.

The following are equivalent

  1. (1)

A graph is $3$-edge bottlenecked.

  2. (2)

The intersection of any two distinct cycles in $G$ is empty or connected.

  3. (3)

A graph does not contain $D_{4}$ as a minor.

###### Proof.

$1\implies 2$ Let $G$ be a $3$-edge bottlenecked graph with cycles $C_{1}$ and
$C_{2}$. Assume to a contradiction that $C_{1}\cap C_{2}$ is nonempty and not
connected. This gives that there are points $x,y\in C_{1}\cap C_{2}$ such that
no $x,y$ path is contained in $C_{1}\cap C_{2}$. Consider the set $X$ to be
the connected component of $C_{1}\cap C_{2}$ containing $x$. Take the sets
$r_{1},r_{2},r_{3},r_{4}$ to be the segments of $C_{1}\cup C_{2}\setminus
C_{1}\cap C_{2}$ adjoined to $X$. Then take the set $Y$ to be all of
$C_{1}\cup C_{2}$ aside from $X$ and the $r_{i}$ sets. The $r_{i}$ segments
give 4 internally disjoint $X,Y$ paths, contradicting condition $1$. ∎

###### Proof.

$2\implies 3$ Let $G$ be a graph where the intersection of any two distinct
cycles is empty or connected and assume to a contradiction that $G$ contains a
$D_{4}$ minor. By considering 3 of the edges in this $D_{4}$ minor there is a
$D_{3}$ minor, and thus a $D_{3}$ subdivision. By considering the shortest
paths between the vertices of this $D_{3}$ subdivision that use the remaining
edge of the $D_{4}$ minor, there are two cycles with a disconnected
intersection and this is a contradiction. ∎

###### Proof.

$3\implies 1$ If a graph is not $3$-edge bottlenecked then there are sets $X$
and $Y$ with at least 4 paths that share no edges between them. By contracting
each path to an edge and the sets $X$ and $Y$ to vertices a $D_{4}$ minor is
produced, contradicting condition $3$. ∎

######  Proposition 4.5.

If a graph contains a $4$-ladder then it contains a $4$-ladder where the poles
are paths, and the connections of two rungs occur at each of the endpoints of
each path.

###### Proof.

Let $G$ be a graph that contains a $4$-ladder, there are two cycles in $G$
that have an intersection that is not connected, pick one connected region of
this intersection to be one pole, and the arcs along each cycle to the next
connected region to be the rungs, now follow the path of one cycle to connect
the shared endpoints of the rungs to form a $4$-ladder with the required
structure. ∎

###  4.4. $n$-edge bottlenecking

######  Theorem 4.1.

The following are equivalent:

  1. (1)

A graph $G$ is $n$-edge bottlenecked.

  2. (2)

Every minor of $G$ is $n$-edge bottlenecked.

  3. (3)

$G$ does not contain $D_{n+1}$ as a minor.

###### Proof.

$1\iff 2$ The backwards direction is straight-forward as $G$ is a minor of
itself. So assume to a contradiction that $G$ is $n$-edge bottlenecked for
some $n\in\mathbb{N}$ and that there is some minor $H$ of $G$ that is not $n$
bottlenecked. This gives that there are $X,Y\subset V(H)$ such that there are
at least $(n+1)$-edge independent $X,Y$ paths. By considering the sets in $G$
that contract to form $X,Y$ and these paths one can construct an
$(n+1)$-ladder in $G$. This would imply that $G$ is not $n$-edge bottlenecked,
a contradiction.

$2\iff 3$ If $G$ contains $D_{n+1}$ as a minor it is clear that $G$ is not
$n$-edge bottlenecked. So let $G$ be a graph that does not contain a $D_{n+1}$
minor and assume to a contradiction that $G$ is not $n$ bottlenecked. As $G$
is not $n$-edge bottlenecked there are $X,Y\subset V(G)$ with $(n+1)$-edge
independent paths between them. By picking the first edge on each path with an
endpoint not in $X$ and contracting all of $X,Y$ and the rest of these paths
to points gives a $D_{n+1}$ minor. ∎

######  Remark 4.4.

Theorem 4.1 shows that the class of $n$ bottlenecked graphs is a minor closed
family classified by the $D_{n+1}$ excluded minor.

##  5\. Coarse Bottlenecking & A Coarse Menger-type Theorem

######  Remark 5.1.

Remark 2.2 Gives ladders as a useful tool for studying edge bottlenecking. As
a $M$-fat $(n+1)$-ladder is not $M$-fat $n$ bottlenecked, the converse of this
statement would be a slightly different version of the coarse Menger
Conjecture than previously proposed [9, 12] and disproven by a counterexample
[11]. Note that the counter example given does not apply in this case as it
contains a fat $3$ ladder. We present one such statement below.

######  Theorem 5.1.

Consider the following conditions:

  1. (1)

A graph $G$ is $M$-fat $n$ bottlenecked.

  2. (2)

Every minor of $G$ is $M$-fat $n$ bottlenecked.

  3. (3)

$G$ does not contain a $M$-fat $D_{n+1}$ minor.

  4. (4)

Every $M$-fat minor of $G$ is $n$-bottlenecked.

  5. (5)

$G$ does not contain a $M$-fat $n+1$ ladder

The implications $1\iff 2\implies 3\iff 4\iff 5$ hold. Furthermore if the
graph is coarsely bottlenecked then $5\implies 1$.

###### Proof of Theorem 5.2.

The implications $2\implies 3$ and $3\iff 5$ are clear. The implications
$3\iff 4$ and $1\iff 2$ are proven by Lemmas 5.1 and 5.2 respectively. The
implication $5\implies 1$ is proven as a result of Theorem 5.2 for coarsely
bottlenecked graphs. ∎

######  Lemma 5.1.

$1\iff 2$ A graph $G$ is $M$-fat $n$ bottlenecked iff every minor of $G$ is
$M$-fat $n$ bottlenecked.

###### Proof.

The direction $2\implies 1$ is straight-forward as $G$ is a minor of itself.
We will prove $1\implies 2$ by a contradiction. So assume to a contradiction
that $G$ is $M$-fat $n$ bottlenecked for some $M$ and that there is some $H$ a
minor of $G$ that is not $M$-fat $n$ bottlenecked. This gives that there are
$M$-disjoint $X,Y\subset H$ such that there are at least $n+1$ $M$-disjoint
$X,Y$ paths. By considering the sets in $G$ that contract to form $X,Y$ and
these paths one can construct a $M$-fat $(n+1)$-ladder in $G$. This would
imply that $G$ is not $M$-fat $n$ bottlenecked, a contradiction. ∎

######  Lemma 5.2.

$3\iff 4$ A graph $G$ does not contain a $M$-fat $n+1$ ladder iff Every
$M$-fat minor of $G$ is $n$-bottlenecked.

###### Proof.

The direction $3\implies 4$ is straight forward. We next will prove $\not
3\implies\not 4$ let $G$ contain a graph $H$, that is not $n$-edge
bottlenecked as a $M$-fat minor. As $H$ is a $M$-fat minor of $G$, $G$
contains every minor of $H$ as an $M$-fat minor. Since $H$ is not $n$-edge
bottlenecked $H$ contains $D_{n+1}$ as a minor 4.1. So $G$ contains $D_{n+1}$
as a $M$-fat minor showing that $4$ can not hold. ∎

The analog in a non-coarse setting of the implication $5\implies 1$ is given
in Remark 2.2 and follows as a direct result of Menger’s Theorem [3]. While it
has been shown [11] that a coarse Menger’s Theorem (as proposed by [9, 4])
does not hold however, bottlenecking is closely related, but weaker than
connectivity. Furthermore the existing counter example relies on large binary
trees with connections across the lower layers, and as these structures get
big they are not coarsely bottlenecked. So there is reason to hope that a
similar statement, pertaining to coarse bottlenecking may be true. In a prior
version of this paper [8] the authors proposed a ”Coarse Menger-type
Conjecture” to serve as the implication $5\implies 1$. This conjecture was
notably different from prior formulations of the Coarse Menger Conjecture [9,
4] as $M$-fat bottlenecking deals only with connected sets that are
$M$-disjoint and the existing counter-example [11] \- in addition to not being
coarsely bottlenecked - uses intersecting sets that are disconnected. In
Theorem 5.2 we prove the original conjecture - under the assumption that the
graph is coarsely bottlenecked. We now provide the following refined Menger-
type conjecture that would, if true, show that this assumption is unnecessary.

######  Conjecture 5.1.1.

(A coarse Menger-type conjecture) If a graph is not coarsely bottlenecked, it
must contain $D_{n}$ as an asymptotic minor for every $n\in\mathbb{N}$.

######  Theorem 5.2 (A coarse Menger-type theorem for coarsely bottlenecked
graphs).

If a graph $G$ is $m$-fat $n+1$ bottlenecked but not coarsely $n$
bottlenecked, $G$ contains $D_{n+1}$ as an asymptotic minor.

###### Proof.

We will show $G$ contains $D_{n+1}$ as an asymptotic minor by constructing a
$M$-fat $n+1$-ladder in $G$ for arbitrarily large $M$. See Figure 2.

Let $M>1$, as $G$ is not coarsely $n$-bottlenecked, for $B>2(M+m+1)$, there
exist connected $B$-disjoint sets $X$ and $Y$ such that no collection of $n$
$B$-balls will intersect every $X,Y$ path. However as $G$ is $m$-fat
$n+1$-bottlenecked there is a collection of $n+1$ vertices
$R:=r_{1},r_{2}...r_{n+1}$ such that $N_{m}(R)$ intersects every $X,Y$ path.

Note that $d(r_{i},r_{j})>2(B-m)$ for all $i\neq j$, else a $B$-ball around
the midpoint of $r_{i},r_{j}$ would enclose $N_{m}(r_{j})$ and $N_{m}(r_{i})$,
contradicting the assumption that $n$ $B$-balls cannot intersect every $X,Y$
path. As the $r_{i}$ are each pairwise $2(B-m)$-disjoint, $m+2M+1$
neighborhoods around them are disjoint so $N_{m+M+1}(R)$ consists of $n+1$
pairwise $M$-disjoint components. These will form the rungs of our ladder.

Next we will construct sets $X_{P}$ and $Y_{P}$ to form the poles. The set
$X_{P}$ is the union of the set $X$ and each component of $G\setminus
N_{m+M}(R)$ that contains a part of $X$. This set is connected as the set $X$
is connected. The set $Y_{P}$ is constructed similarly.

As $X$ and $Y$ are disconnected in $G\setminus N_{m}(R)$, the components of
$G\setminus N_{m+M}(R)$ that intersect $X$ are $2M$-disjoint from the
components intersecting $Y$. Furthermore, as every $X,Y$ path intersects
$N_{m}(R)$, the set $X$ is $M$-disjoint from components of $N_{m+M}(R)$ that
intersect $Y$. A symmetric argument shows that the sets $X_{P}$ and $Y_{P}$
are $M$-disjoint.

As the poles and rungs are $M$-disjoint, these sets give a $M$-fat $n+1$
ladder. ∎

Figure 2. Picture proof of theorem 5.2 The set $X$ is on the left in blue
hashing, while the set $Y$ on the right in pink hashing. All $X,Y$ paths are
in the crosshatched region. Components of $G\setminus N_{m+M}(R)$ are blue if
they touch $X$ or pink if they touch $Y$. By construction, these components
are $M$-disjoint from $N_{m}(R)$. $X$ and $Y$ can enter an $m$ balls, but
never the same one nor cross through $N_{m}(R)$ on an $X,Y$ path, as this
would lead to contradiction. The poles $X_{p}$ (everything blue), and $Y_{p}$
(everything pink) are $M$-disjoint as they are separated by $M$ long portions
of the $X,Y$ paths between the $m$ balls and the $M+m$ balls. The $m+2M+1$
balls don’t overlap as this would contradict $B>2(M+m+1)$, so the rungs formed
by the components of $N_{m+M+1}(R)$ are $M$-disjoint from each other.

######  Remark 5.2.

Theorem 5.2 shows that a coarsely bottlenecked graph that is not $n$
bottlenecked must contain an asymptotic $D_{n+1}$ minor, and this implies the
existence of a $M$-fat $D_{n^{\prime}}$ minor for all $M$ and $n^{\prime}\leq
n+1$. Thus if a coarsely bottlenecked graph does not contain an $M$-fat $n+1$
ladder for some $M$ and $n$ it must be $M$-fat $n$-bottlenecked.

Theorem 5.1, along with Theorem 5.2 shows that the class of $M$-fat $n$
bottlenecked graphs is a minor closed family classified by the $M$-fat
$D_{n+1}$ excluded minor.

######  Theorem 5.3.

Consider the conditions:

  1. (1)

A graph $G$ is not coarsely $n$ bottlenecked.

  2. (2)

$G$ contains $D_{n+1}$ as an asymptotic minor.

  3. (3)

$G$ contains a $(n+1)$-ladder as an asymptotic minor.

The implications $2\iff 3\implies 1$ hold. Furthermore if the graph is
coarsely bottlenecked then $1\implies 2$.

###### Proof of Theorem 5.3.

The implications $2\iff 3\implies 1$ hold as a result of Theorem 5.1. In
coarsely bottlenecked graphs $1\implies 2$ as a result of Theorem 5.2. In
cases where $1\implies 3$ holds, this gives an excluded asymptotic minor
characterization of coarsely bottlenecked graphs. ∎

In [9] Georgakopoulos and Papasoglu proposed the following conjecture.

######  Conjecture 5.3.1 ([9] Conjecture 1.1).

Let $X$ be a graph or a length space, and let $H$ be a finite graph. Then $X$
has no $M$-fat $H$ minor for some $M\in\mathbb{N}$ if and only if $X$ is
quasi-isometric to a graph with no $H$ minor. Furthermore, the constants of
this quasi-isometry depend only on $M$ and $H$.

######  Remark 5.3.

Recently [10] the counter example to the coarse Menger conjecture of [9] and
[4] was adapted to a counterexample of Conjecture 5.3.1. In a similar spirit,
we propose the following conjecture for the class of coarsely bottlenecked
graphs.

######  Conjecture 5.3.2 (Quasi $n$-Bottlenecking Conjecture).

If a graph $G$ is coarsely $n$ bottlenecked then it is quasi-isometric to a
$n$-edge bottlenecked graph.

######  Remark 5.4.

The Quasi-Bottlenecking conjecture 5.3.2 holds in the case of $n=1$ [2, 9] and
$n=2$ [1, 4]. If Conjecture 5.1.1 holds, Conjecture 5.3.2 is a special case of
Conjecture 5.3.1, as 5.1.1 together with Theorem 5.2 would imply that coarse
$n$-bottlenecking is characterized by an excluded asymptotic $D_{n+1}$ minor.
So Conjecture 5.3.2 would imply that a graph with no asymptotic $D_{n}$ minor
is quasi-isometric to a graph with no $D_{n}$ minor.

## References

  * [1] Fujiwara, Koji, and Panos Papasoglu. “A coarse-geometry characterization of cacti.” arXiv preprint arXiv:2305.08512 (2023).
  * [2] Manning, Jason Fox. “Geometry of Pseudocharacters.” Geometry & Topology, vol. 9, no. 2, June 2005.
  * [3] Menger, K. (1927). Zur allgemeinen kurventheorie. Fundamenta Mathematicae, 10(1), 96-115.
  * [4] Albrechtsen, S., Huynh, T., Jacobs, R. W., Knappe, P., & Wollan, P. (2023). The induced two paths problem. arXiv preprint arXiv:2305.04721 (2023).
  * [5] Bondy, J.A. & Murty, U.S.R. (2008). Graph Theory. Graduate Texts in Mathematics
  * [6] Roe, J. (2003). Lectures on coarse geometry (No. 31). American Mathematical Soc..
  * [7] Bruner, M., Mitra, A., & Steiger H. Graph Skeletons and Diminishing Minors. arXiv preprint arXiv:2405.17785 (2024).
  * [8] Bruner, M., Mitra, A., & Steiger H. Bottlenecking in graphs and a Menger-type conjecture arXiv preprint arXiv:2406.07802v1
  * [9] Georgakopoulos, A., & Papasoglu, P. (2023). Graph minors and metric spaces. arXiv preprint arXiv:2305.07456.
  * [10] Davies, J., Hickingbotham, R., Illingworth, F., & McCarty, R. (2024). Fat minors cannot be thinned (by quasi-isometries). arXiv preprint arXiv:2405.09383.
  * [11] Albrechtsen, S., Huynh, T., Jacobs, R. W., Knappe, P., & Wollan, P. (2023). The induced two paths problem. arXiv preprint arXiv:2305.04721.
  * [12] Chepoi, V., Dragan, F. F., Newman, I., Rabinovich, Y., & Vaxes, Y. (2012). Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs. Discrete & Computational Geometry, 47, 187-214.


On asymorphisms of finitary coarse spaces

I.V. Protasov

Abstract. We characterize finitary coarse spaces $X$ such that every
permutation of $X$ is an asymorphism.

2010 MSC: 54E05, 54E35.

Keywords: bornology, coarse space, asymorphism.

##  1 Introduction and results

Given a set $X$, a family $\mathcal{E}$ of subsets of $X\times X$ is called a
coarse structure  on $X$ if

  * •

each $E\in\mathcal{E}$ contains the diagonal $\bigtriangleup_{X}$,
$\bigtriangleup_{X}=\\{(x,x)\in X:x\in X\\}$;

  * •

if $E$, $E^{\prime}\in\mathcal{E}$ then $E\circ E^{\prime}\in\mathcal{E}$ and
$E^{-1}\in\mathcal{E}$, where $E\circ E^{\prime}=\\{(x,y):\exists z((x,z)\in
E,\ \ (z,y)\in E^{\prime})\\}$, $E^{-1}=\\{(y,x):(x,y)\in E\\}$;

  * •

if $E\in\mathcal{E}$ and $\bigtriangleup_{X}\subseteq E^{\prime}\subseteq E$
then $E^{\prime}\in\mathcal{E}$;

  * •

$\bigcup\mathcal{E}=X\times X$.

A subfamily $\mathcal{E}^{\prime}\subseteq\mathcal{E}$ is called a base for
$\mathcal{E}$ if, for every $E\in\mathcal{E}$, there exists
$E^{\prime}\in\mathcal{E}^{\prime}$ such that $E\subseteq E^{\prime}$. For
$x\in X$, $A\subseteq X$ and $E\in\mathcal{E}$, we denote

$E[x]=\\{y\in X:(x,y)\in E\\},\ E[A]=\bigcup_{a\in A}\ E[a]$

and say that $E[x]$ and $E[A]$ are balls of radius $E$ around $x$ and $A$.

The pair $(X,\mathcal{E})$ is called a coarse space [6] or a ballean [4], [5].

For a coarse space $(X,\mathcal{E})$, a subset $B\subseteq X$ is called
bounded if $B\subseteq E[x]$ for some $E\in\mathcal{E}$ and $x\in X$. The
family $\mathcal{B}_{(X,\mathcal{E})}$ of all bounded subsets of
$(X,\mathcal{E})$ is called the bornology of $(X,\mathcal{E})$. We recall that
a family $\mathcal{B}$ of subsets of a set $X$ is a bornology if $\mathcal{B}$
is closed under taking subsets and finite unions, and $\mathcal{B}$ contains
all finite subsets of $X$.

Let $(X,\mathcal{E})$, $(X^{\prime},\mathcal{E}^{\prime})$ be coarse spaces. A
mapping $f:X\longrightarrow X^{\prime}$ is called

  * •

bornologous if $f(B)\in\mathcal{B}_{(X^{\prime},\mathcal{E}^{\prime})}$ for
each $B\in\mathcal{B}_{(X,\mathcal{E})}$;

  * •

macro-uniform if, for each $E\in\mathcal{E}$, there exists
$E^{\prime}\in\mathcal{E}^{\prime}$ such that, for all $x,y\in X$, $(x,y)\in
E$ implies $(f(x),f(y))\in E^{\prime}$;

  * •

asymorphism if $f$ s a bijection and $f,f^{-1}$ are macro-uniform.

We recall that a coarse space $(X,\mathcal{E})$ is discrete (or thin) if, for
each $E\in\mathcal{E}$, there exists $B\in\mathcal{B}_{(X,\mathcal{E})}$ such
that $E[x]=\\{x\\}$ for each $x\in X\setminus B$. Every bornology
$\mathcal{B}$ on a set $X$ defines the discrete coarse space
$(X,\mathcal{E}_{\mathcal{B}})$ with the base $\\{E_{B}:B\in\mathcal{B}\\}$,
were $E_{B}[x]=B$ if $x\in B$, and $E_{B}[x]=\\{x\\}$ if $x\in X\setminus B$.
Every discrete coarse space $(X,\mathcal{E})$ coincides with
$(X,\mathcal{E}_{\mathcal{B}})$ for
$\mathcal{B}=\mathcal{B}_{(X,\mathcal{E})}$.

For different characterizations of discrete coarse spaces, see Theorem 2.2 in
[1].

Theorem 1. Every bornologous mapping $f:X\longrightarrow X$ of a coarse space
$(X,\mathcal{E})$ is macro-uniform if and only if $(X,\mathcal{E})$ is
discrete.  A coarse space $(X,\mathcal{E})$ is called

  * •

locally finite if each ball $E[x]$ is finite, equivalently,
$\mathcal{B}_{(X,\mathcal{E})}=[X]^{<\omega}$;

  * •

finitary  if, for each $E\in\mathcal{E}$ there exists a natural number $n$
such that $|E[x]|<n$ for each $x\in X$.

Let $G$ be a transitive group of permutations of a set $X$. We denote by
$X_{G}$ the set $X$ endowed with the coarse structure with the base

$\\{\\{(x,gx):g\in F\\}:F\in[G]^{<\omega},\ \ id\in F\\}.$

By [2, Theorem 1], for every finitary coarse structure $(X,\mathcal{E})$,
there exists a transitive group $G$ of permutations of $X$ such that
$(X,\mathcal{E})=X_{G}$. For more general results, see [3].

Let $X$ be a set, $\kappa$ be a cardinal, $\mathcal{S}_{X}$ denotes the group
of all permutations of $X$,
$\mathcal{S}_{X}^{<\kappa}=\\{g\in\mathcal{S}_{X}:|supp\ g|<\kappa\\}$, $supp\
g=\\{x\in X:g(x)\neq x\\}$.

Theorem 2. Let $(X,\mathcal{E})$ be an infinite finitary coarse space. Then
the following statements are equivalent

$(i)$ every permutation of $X$ is an asymorphism of $(X,\mathcal{E})$;

$(ii)$ there exists an infinite cardinal $\kappa$, $\kappa\leq|X|^{+}$ such
that $(X,\mathcal{E})=X_{G}$ for $G=\mathcal{S}_{X}^{<\kappa}$.

Open problem. Characterize locally finite coarse spaces $(X,\mathcal{E})$ such
that every permutation of $X$ is an asymorphism.

##  2 Proofs

Proof of Theorem 1.

Let $(X,\mathcal{E})$ be a discrete coarse space defined by a bornology
$\mathcal{B}$ and let $f:X\longrightarrow X$ is bornologous. We take an
arbitrary $B\in\mathcal{B}$ and note that $f(E_{B}[x])\subseteq
E_{f(B)}[f(x)]$ for each $x\in X$, so $f$ is macro-uniform.

On the other hand, let $(X,\mathcal{E})$ is not discrete. Then there exists
$E\in\mathcal{E}$ such that, for each bounded subset $B$ of $(X,\mathcal{E})$,
one can find $x\in X\setminus B$ such that $|E[x]|>1$. Therefore, for some
ordinal $\lambda$, we can choose inductively two injective $\lambda$-sequences
$(x_{\alpha})_{\alpha<\lambda}$, $(y_{\alpha})_{\alpha<\lambda}$ such that the
set $\\{x_{\alpha}:\alpha<\lambda\\}$ is unbounded, $y_{\alpha})\in
E[x_{\alpha}]$, $\alpha<\lambda$ and $y_{\alpha}\neq x_{\beta}$ for all
$\alpha,\beta<\lambda$.

We define a mapping $f:X\longrightarrow X$ by $f(y_{\alpha})=y_{0}$ for each
$\alpha<\lambda$, and $f(x)=x$ for each $x\in
X\setminus\\{y_{\alpha}:\alpha<\lambda\\}$. Clearly, $f$ is bornologous. Since
$\\{x_{\alpha}:\alpha<\lambda\\}$ is unbounded, $f(x_{\alpha})=x_{\alpha}$,
$y_{\alpha}\in E[x_{\alpha}]$ and $f(y_{\alpha})=y_{0}$ for each
$\alpha<\lambda$, we conclude that $f$ is not macro-uniform. $\ \ \ \Box$

Proof of Theorem 2.

$(i)\Longrightarrow(ii)$. We say that a permutation $g$ of $X$ is compatible
with $\mathcal{E}$ if there exists $E\in\mathcal{E}$ such that $(x,gx)\in E$
for each $x\in X$. We note that the set $G$ of all permutations compatible
with $\mathcal{E}$ is a subgroup of $\mathcal{S}_{X}$ and, by Theorem 1 from
[2], $(X,\mathcal{E})=X_{G}$.

We say that a subset $Y$ of $X$ is crowded if there exists $E\in\mathcal{E}$
such that $|E[y]|>1$ for each $y\in Y$. We take the minimal cardinal $\kappa$,
$\kappa\leq|X|^{+}$ such that, for each $\lambda<\kappa$, $(X,\mathcal{E})$
has a crowded subset of cardinality $\lambda$.

We show that $G=\mathcal{S}_{X}^{<\kappa}$. If $g\in G$ then $|supp\
g|<\kappa$ because the set $supp\ g$ is crowded, so
$g\in\mathcal{S}_{X}^{<\kappa}$ and $G\subseteq\mathcal{S}_{X}^{<\kappa}$.

To prove $\mathcal{S}_{X}^{<\kappa}\subseteq G$, we need the following
auxiliary statement.

$(\ast)$ Let $Y$ be a subset of $X$ such that $|Y|=|X|$, $\lambda$ be a
cardinal, $\lambda<\kappa$. Then there exists two injective
$\lambda$-sequences $(x_{\alpha})_{\alpha<\lambda}$,
$(y_{\alpha})_{\alpha<\lambda}$ in $Y$ and $H\in\mathcal{E}$ such that
$\\{x_{\alpha}:\alpha<\lambda\\}\cap\\{y_{\alpha}:\alpha<\lambda\\}=\emptyset$
and $(x_{\alpha},y_{\alpha})\in H$ for each $\alpha<\lambda$.

By the choice of $\kappa$, we can choose $E\in\mathcal{E}$ and injective
$\lambda$-sequences $(a_{\alpha})_{\alpha<\lambda}$,
$(b_{\alpha})_{\alpha<\lambda}$ such that $\\{a_{\alpha}:\alpha<\lambda\\}\
\bigcap\ \ \\{b_{\alpha}:\alpha<\lambda\\}=\emptyset$ and
$(a_{\alpha},b_{\alpha})\in E$ for each $\alpha<\lambda$. Passing to
subsequences, we may suppose that $|Y\setminus\\{a_{\alpha},\
b_{\alpha}:\alpha<\lambda\\}|=|X|.$ We choose two injective
$\lambda$-sequences $(x_{\alpha})_{\alpha<\lambda}$,
$(y_{\alpha})_{\alpha<\lambda}$ in $Y\setminus\\{a_{\alpha},\
b_{\alpha}:\alpha<\lambda\\}$ such that $\\{x_{\alpha}:\alpha<\lambda\\}\
\cap$ $\\{y_{\alpha}:\alpha<\lambda\\}=\emptyset$. Then we define an
involution $f$ of $X$ by $fa_{\alpha}=x_{\alpha}$, $fb_{\alpha}=y_{\alpha}$
and $fx=x$ for each $x\in X\setminus\\{a_{\alpha},\ b_{\alpha},\ x_{\alpha},\
y_{\alpha}:\alpha<\lambda\\}$. Since $f$ is macro-uniform, there exists
$H\in\mathcal{E}$ such that $(x,y)\in E$ implies $(fx,fy)\in H$. Hence,
$(x_{\alpha},y_{\alpha})\in H$ for each $\alpha<\lambda$.

Now let $g\in\mathcal{S}_{X}^{<\kappa}$, $A=supp\ g$. We prove that $g$ is
compatible with $\mathcal{E}$, so $g\in G$. By the 3-Sets Lemma, there exists
a partition $A_{1},A_{2},A_{3}$ of $A$ such that $A_{i}\bigcap
gA_{i}=\emptyset$, $i\in\\{1,2,3\\}$. We suppose that
$|X\setminus(A_{1}\bigcup gA_{1}))|=|X|$, denote $Y=|X\setminus(A_{1}\bigcap
gA_{1})|$, $\lambda=|A_{1}|$ and apply $(\ast)$ to choose corresponding
$(x_{\alpha})_{\alpha<\lambda}$, $(y_{\alpha})_{\alpha<\lambda}$ and
$H\in\mathcal{E}$. We enumerate $A_{1}=\\{a_{\alpha}:\alpha<\lambda\\}$ and
define an involution $h$ of $X$ by $hx_{\alpha}=a_{\alpha}$,
$hy_{\alpha}=ga_{\alpha}$ and $hx=x$ for each $x\in
X\setminus\\{x_{\alpha},y_{\alpha},a_{\alpha},ga_{\alpha}:\alpha<\lambda\\}$.
Since $h$ is macro-uniform, there exists $K\in\mathcal{E}$ such that $(x,y)\in
H$ implies $(hx,hy)\in K$. Hence, $(a_{\alpha},ga_{\alpha})\in K$ for each
$\alpha<\lambda$.

If $|X\setminus(A_{1}\cup gA_{1})|<|X|$ then we partition $A_{1}=B\cup C$,
$|B|=|C|=|X|$ and, to choose $K$, apply above arguments for the pair $B,gB$
and $C,gC$.

Repeating above construction for $A_{2}$ and $A_{3}$, we see that $g$ is
compatible with $\mathcal{E}$.

$(ii)\Longrightarrow(i)$. Let $G=\mathcal{S}_{X}^{<\kappa}$,
$(X,\mathcal{E})=X_{G}$. We take an arbitrary $h\in\mathcal{S}_{X}$ and show
that $h:X_{G}\rightarrow X_{G}$ is macro-uniform.

Let $F$ be a finite subset of $\mathcal{S}_{X}^{<\kappa}$, $x\in X$, $y=hx$.
Then $hFh^{-1}\subset\mathcal{S}_{X}^{<\kappa}$ and, for $f\in F$, we have
$(hx,hfx)=(y,hfh^{-1}y)$, so $h$ is macro-uniform. $\ \ \Box$

## References

  * [1] D. Dikranjan, I. Protasov, K. Protasova, N. Zava, Balleans, hyperballeans and ideals, Appl. Gen. Topology 20 (2019), 431-447.
  * [2] I. V Protasov, Balleans of bounded geometry and $G$-spaces, Algebra Discrete Math. 7: 2 (2008), 101-108.
  * [3] I. Protasov, Decompositions of set-valued mappings,  Algebra Discrete Math. 30: 2 (2020), 235-238.
  * [4] I. Protasov, T. Banakh, Ball Structures and Colorings of Groups and Graphs, Math. Stud. Monogr. Ser., vol. 11, VNTL, Lviv, 2003.
  * [5] I. Protasov, M. Zarichnyi, General Asymptology, Math. Stud. Monogr. Ser., Vol. 12, VNTL, Lviv, 2007.
  * [6] J. Roe, Lectures on Coarse Geometry, Univ. Lecture Ser., vol. 31, American Mathematical Society, Providence RI, 2003.

CONTACT INFORMATION

I. Protasov:
Faculty of Computer Science and Cybernetics
Taras Shevchenko National University of Kyiv
Academic Glushkov pr. 4d
03680 Kyiv, Ukraine
<EMAIL_ADDRESS>