A gentle intro to coarse graph theory, part 1

These are notes for a mini-course on coarse graph theory that I taught at the ISM discovery school Recent advances in probability and combinatorics in June 2026. The notes are currently a draft! Some content including references may be missing or incomplete at the moment.

1. Motivation

Coarse graph theory broadly refers to the recent research in structural graph theory focused on understanding the “large-scale” structure of graphs. Of particular interest is to understand when two different graphs have approximately the same large-scale structure. Let’s gather intuition about what this means by looking at three examples of situations in which understanding the “large-scale” similarities between graphs is useful.

1.1 Intuitively similar graphs

The first and simplest example starts with the following observation: we seem to have an intuitive notion of what it means for two graphs to be similar. Consider the four graphs pictured in Figure 1 below. If you were asked to pair them up into two pairs of similar graphs, I’m betting that you would be able to do so, even though I have not given a definition of what it means for two graphs to be similar.

In this example, these pairings have the potential to be useful beyond just capturing a visual similarity. Graph (a) is planar and graph (c) is a tree. Both planar graphs and trees are examples of well-structured and well-understood graph classes. If we could formalize the idea that graph (b) is “approximately” a tree, or that graph (d) is “approximately” a planar graph, we could then try to use the nice properties of trees and planar graphs to understand the structure of graphs (b) and (d), even though they are not members of those classes themselves.

1.2 Representing surfaces with graphs

The next example comes from a talk by Agelos Georgakopoulos. Suppose that we want to understand the structure of some surface $\Sigma$. Being graph-theorists (bear with me), we would like to model $\Sigma$ with a graph. There is a natural way to do this: throw a bunch of vertices onto $\Sigma$ so that every point in $\Sigma$ is close to at least one vertex, and put edges between two vertices that are close together. This procedure will create a graph $G$ that models the surface $\Sigma$.

If you and I independently follow this procedure to make a graph to model $\Sigma$, we will almost certainly not make the same graph. But since both of our graphs were formed from the surface $\Sigma$, we might hope that our graphs are “similar,” in the sense that they both capture some of the same properties of $\Sigma$. Concretely, if we want our graphs to both approximate the metric on $\Sigma$, then we would hope that the metrics on our graphs are similar to each other.

1.3 Representing groups as Cayley graphs

Finally, we consider an example from group theory, which is where the ideas behind coarse graph theory originated. Let $\Gamma$ be a finitely generated group. As graph-theorists (again), we would like to model $\Gamma$ with a graph. There is a natural way to represent groups as graphs, called Cayley graphs. Given a finitely generated group $\Gamma$ and a finite generating set $S$ of $\Gamma$, the Cayley graph $Cay(\Gamma, S)$ is the graph with vertex set $\Gamma$ and edge set ${gg’ : g’=g \cdot s \mid s \in S,\ g, g’ \in \Gamma}$.

Now we run into a similar problem as in the previous example. We want to understand the group $\Gamma$ using a Cayley graph, but the graph we obtain depends on the finite generating set $S$. For instance, two different Cayley graphs for the group $\mathbb{Z}$ are shown in Figure 2.

What we would like to say is that although these two graphs are different, they are “approximately the same” if we zoom out and consider only the “large-scale” structure of the graphs. Specifically, in this case, these graphs are both approximately the two-way infinite path. Indeed, the graph on the left is in fact the two-way infinite path, and the graph on the right is approximately the two-way infinite path, with only local differences.

1.4 Outlook

Our hope in each of these examples is that the right notion of graph similarity allows us to use graphs to understand other structures, like more complex graphs, surfaces, and groups. In the next section, we introduce the idea of quasi-isometries to fill this role.

2. Quasi-isometry

2.1 Definition of quasi-isometry

Given a graph $G$, we denote by $d_G$ the graph distance on $G$. For every pair of vertices $x, y$ of $G$, the distance $d_G(x, y)$ is equal to the length of the shortest path from $x$ to $y$ in $G$.

An $(M, A)$-quasi-isometry from $G$ to $H$ is a map $\varphi: V(G) \to V(H)$ satisfying the following conditions:

(i) $\dfrac{1}{M} \cdot d_G(x, y) - A \leq d_H(\varphi(x), \varphi(y)) \leq M \cdot d_G(x, y) + A$ for every pair $x, y \in V(G)$; and

(ii) for every $z \in V(H)$ there exists $x \in V(G)$ such that $d_H(z, \varphi(x)) \leq A$.

In the notation for $(M, A)$-quasi-isometry, $M$ stands for the multiplicative distortion and $A$ stands for the additive distortion. Condition (i) of the definition says that distances are approximately preserved by the quasi-isometry map $\varphi$, up to the multiplicative and additive distortions. Condition (ii) says that the map $\varphi$ is almost surjective: every vertex of $H$ is close to a vertex in the image of $\varphi$.

Condition (ii) is necessary since we want to use a quasi-isometry from $G$ to $H$ to claim that the graph $G$ is “similar” to the graph $H$. Concretely, the quasi-isometry implies that the graph metrics of $G$ and $H$ are similar; this is the point of condition (i). Without condition (ii), the map $\varphi$ could map all of $G$ to only a small part of $H$. In this case, $\varphi$ says nothing about whether the part of $H$ far from the image of $\varphi$ has anything in common with the graph $G$.

The idea of quasi-isometry between graphs can be applied in different contexts. If all of the relevant graphs are infinite (e.g. if all relevant graphs are Cayley graphs of infinite groups), then the notion of quasi-isometry is sensible even without universal constants $M$ and $A$. Two (infinite) graphs $G$ and $H$ are quasi-isometric if there exist finite constants $M$ and $A$ such that $G$ is $(M, A)$-quasi-isometric to $H$.

If our graphs $G$ and $H$ are finite, on the other hand, then the formulation without explicit constants is too weak: every finite graph is quasi-isometric to a single vertex. Indeed, for any two fixed finite graphs $G$ and $H$, there exist constants $M$ and $A$ such that $G$ is $(M, A)$-quasi-isometric to $H$.

For this reason, we are very often interested in statements that relate two graph classes via quasi-isometry. Let $\mathcal{G}$ and $\mathcal{H}$ be graph classes. We say that graphs in $\mathcal{G}$ are $(M, A)$-quasi-isometric to graphs in $\mathcal{H}$ if there exist constants $M$ and $A$ such that for every graph $G$ in $\mathcal{G}$, there is a graph $H$ in $\mathcal{H}$ such that $G$ is $(M, A)$-quasi-isometric to $H$. It is essential that the constants $M$ and $A$ depend only on the graph classes $\mathcal{G}$ and $\mathcal{H}$, and not on the specific graphs $G$ and $H$.

2.2 Quasi-isometry properties

Quasi-isometries have a number of properties, and it is useful to be familiar with them. I’ve listed a few properties here as exercises:

1. Prove that the graph distance $d_G$ is a metric.
2. Prove that quasi-isometry without explicit constants is an equivalence relation.
3. Prove that the two Cayley graphs of $\mathbb{Z}$ in Figure 2 are quasi-isometric.
4. Prove that if there is a $(M, A)$-quasi-isometry from $G$ to $H$, then there exist constants $M’$ and $A’$ which depend only on $M$ and $A$ such that there is an $(M’, A’)$-quasi-isometry from $H$ to $G$.
5. Find constants $M$ and $A$ and an $(M, A)$-quasi-isometry from graph (b) to graph (c) from Figure 1.
6. Suppose $\varphi: G \to H$ is an $(M, A)$-quasi-isometry. Prove that if $x$ and $y$ are vertices in the same connected component of $G$, then $\varphi(x)$ and $\varphi(y)$ are vertices in the same connected component of $H$. Deduce that if $G$ is connected, then $H$ is connected.

2.3 Voronoi construction of quasi-isometries

In this section, we justify the term “coarse” by discussing a way to construct a quasi-isometry from a given graph $G$ to a graph $H$ which is a “coarsening” of $G$.

Let $G$ be a connected graph and fix a positive integer $r > 1$. A vertex-subset $S$ of $G$ is a distance-r independent set if $d_G(x, y) > r$ for every pair of vertices $x, y$ in $S$. A vertex-subset $S$ of $G$ is a maximal distance- $r$ independent set if $S$ is inclusion-maximal with this property. In other words, if $S$ is a maximal distance- $r$ independent set of $G$, then every vertex of $G$ is of distance at most $r$ from a vertex of $S$.

Fix a maximal distance- $r$ independent set $S$ of $G$. We will construct a graph $H$ as follows. Set $V(H) := S$, and set $E(H) := {xy \mid d_G(x, y) \leq 3r}$. In words, the edge set of $H$ consists of pairs of vertices of $S$ that are of distance at most $3r$ in $G$.

Next we define the quasi-isometry $\varphi$ from $G$ to $H$. Let $(P_s)_{s \in S}$ be a partition of the vertex-set of $G$ indexed by the vertices of $S$ such that $d_G(s, x) \leq r$ for every vertex $x \in P_s$. Observe that since $S$ is a maximal distance- $r$ independent set, such a partition always exists. (This partition is not necessarily unique!)

Finally, set $\varphi(x) := s$ for every vertex $x$ in $P_s$ and for every vertex-subset $P_s$.

Lemma 2.1. The mapping $\varphi: G \to H$ defined above is a $(3r, 2r)$-quasi-isometry.

Proof. Fix vertices $x$ and $y$ of $G$. First, we will show that $d_H(\varphi(x), \varphi(y)) \leq r \cdot d_G(x, y) + r$.

Let $P = p_0 \,\text{-}\, \cdots \,\text{-}\, p_k$ with $p_0 = x$ and $p_k = y$ be a shortest path from $x$ to $y$ in $G$. Let $p_0$, $p_{r}$, $p_{2r}$, $p_{3r}$, $\ldots$, $p_k$ be the subsequence of vertices from $P$ formed by starting at $p_0$, choosing the vertex of distance exactly $r$ from the previous vertex, and ending at $p_k$ when $p_k$ is of distance at most $r$ from the previous vertex. Set $q_i := \varphi(p_{ri})$ for $0 \leq i \leq \lfloor \frac{k}{r} \rfloor$ and $q_i := \varphi(p_k)$ for $i = \lfloor \frac{k}{r} \rfloor + 1$.

We claim that for all $0 \leq i < \lfloor \frac{k}{r} \rfloor + 1$, there is an edge between $q_i$ and $q_{i+1}$ in $H$. By the construction of $\varphi$, it holds that $d_G(p_{ri}, q_{i}) \leq r$ and $d_G(p_{r(i+1)}, q_{i+1}) \leq r$. Further, the path $P$ witnesses that $d_G(p_{ri}, p_{r(i+1)}) \leq r$. Therefore, $d_G(q_i, q_{i+1}) \leq 3r$, so there is an edge between $q_i$ and $q_{i+1}$ in $H$.

Now, $Q = q_0 \,\text{-}\, q_1 \,\text{-}\, \cdots \,\text{-}\, q_{\lfloor \frac{k}{r} \rfloor + 1}$ is a path in $H$ from $\varphi(x)$ to $\varphi(y)$ of length $\lfloor\frac{k}{r}\rfloor + 1$. This proves that $d_H(\varphi(x), \varphi(y)) \leq r \cdot d_G(x, y) + r$.

Next we show that $d_G(x, y) \leq 3r \cdot d_H(\varphi(x), \varphi(y)) + 2r$. Let $Q = q_0 \,\text{-}\,\cdots\,\text{-}\, q_k$ with $q_0 = \varphi(x)$ and $q_k = \varphi(y)$ be a shortest path from $\varphi(x)$ to $\varphi(y)$ in $H$. Since $q_i$ is adjacent to $q_{i+1}$ in $H$ only if $d_G(q_i, q_{i+1}) \leq 3r$, there is a path of length at most $3r$ from $q_i$ to $q_{i+1}$ in $G$ for $0 \leq i < k$. By concatenating these paths, we obtain a path $P’$ of length $3r \cdot k$ from $\varphi(x)$ to $\varphi(y)$ in $G$. Finally, we can append a path of length at most $r$ from $x$ to $\varphi(x)$ to the start of $P’$ and a path of length at most $r$ from $\varphi(y)$ to $y$ to the end of $P’$ to form a path $P$ from $x$ to $y$ in $G$ of length at most $3r \cdot d_H(\varphi(x), \varphi(y)) + 2r$.

We have now shown that condition (i) holds. In this construction, the map $\varphi$ is surjective, since $\varphi(x) = x$ for every vertex $x$ of $H$. This proves that condition (ii) holds. Therefore, $\varphi: G \to H$ defined above is a $(3r, 2r)$-quasi-isometry. $\blacksquare$