The n-Category Café

So, take a graph $G$, where by “graph” I mean a finite, undirected graph without loops or multiple edges. The distance between two vertices is the minimum length of a path between them (or $\infty$ if there is no path at all). We now define a square matrix $Z_G$ over $\mathbb{Q}(q)$, the field of rational functions in a formal variable $q$. The rows and columns are indexed by the vertices of $G$, and for vertices $x$ and $y$, the $(x, y)$-entry of $Z_G$ is $q^{d(x, y)}$ (understood to be $0$ if $d(x, y) = \infty$).

It’s easy to see that the element $det(Z_G)$ of $\mathbb{Q}(q)$ is nonzero. (Consider $q = 0$.) Hence $Z_G$ is invertible over $\mathbb{Q}(q)$. The magnitude of $G$ is the sum of all the entries of $Z_G^{-1}$. Thus, the magnitude of a graph is a rational function.

Why might this invariant be interesting? Principally, it’s because it’s a special case of the notion of the magnitude of a metric space, which has proved to be interesting, but has been investigated much more deeply for the kind of spaces that geometers like to think about than for metric spaces arising from graphs.

Last time, I assembled as many examples of graphs and their magnitudes as I could, with the aim of arriving at an intuitive understanding of the magnitude of a graph. The comments thread helped with that. For example, the magnitude of a graph can also be expressed as a power series with integer coefficients, and we discovered an alternating-sum formula for those coefficients. But we’re still in thick murk.

Here’s the main point of this post. Suppose we have a graph $G$, equipped with a pair of distinguished, distinct vertices, $g_+$ and $g_-$. And suppose we also have another such, $(H, h_+, h_-)$. We can make a new graph by gluing $G$ to $H$ along the two basepoints (deleting the duplicate edge if one is created). In fact, we can do this in two ways:

• by gluing $g_+$ to $h_+$ and $g_-$ to $h_-$, we make a new graph $X$;

• by gluing $g_+$ to $h_-$ and $g_-$ to $h_+$, we make a new graph $Y$.

The graphs $X$ and $Y$ are said to differ by a Whitney twist. For instance, these two graphs differ by a Whitney twist:

In case you can’t see the difference between red and green, the graph $G$ is the part from the belt downwards, and the graph $H$ is the part from the belt upwards. Since there is a belt, either $G$ has an edge between its two basepoints, or $H$ does (or both); the picture doesn’t reveal which.

Last time, something extraordinary happened. David Speyer wondered whether graphs differing by a Whitney twist always have the same magnitude. (He wondered this because graphs differing by a Whitney twist always have the same Tutte polynomial.) He tested this idea with an experiment, by getting a computer to see whether it was true for a pair of randomly-generated 10-vertex graphs $G$ and $H$. It was.

The magnitudes of David’s graphs $X$ and $Y$ are rational functions of degree 23, whose coefficients are integers of up to five digits, so it’s barely conceivable that they’d be equal by coincidence. And yet, it’s not true in general that graphs differing by a Whitney twist always have the same magnitude!

Simon Willerton gave a counterexample. Here’s a slightly smaller one: the two graphs

differ by a Whitney twist, but don’t have the same magnitude.

What on earth is going on? Simon suggested a conjecture that would explain the situation. I now have a proof. Here it is:

Theorem   Two graphs differing by a Whitney twist have the same magnitude as long as there is an edge between the two gluing points.

Formally, let $G$ be a graph, and let $g_+$ and $g_-$ be vertices of $G$ joined by an edge. Let $H$ be a graph, and let $h_+$ and $h_-$ be vertices of $H$ joined by an edge. Then the two graphs

$$X = (G \amalg H)\Big/(g_+ = h_+, g_- = h_-), \qquad Y = (G \amalg H)\Big/(g_+ = h_-, g_- = h_+)$$

have the same magnitude.

Let’s pause to consider this condition in the statement of the theorem that the two gluing points are joined by an edge. The following are equivalent:

• there’s an edge between the two gluing points of $X$
• either there is an edge between $g_+$ and $g_-$ in $G$ or there is an edge between $h_+$ and $h_-$ in $H$
• there’s an edge between the two gluing points of $Y$.

Moreover, if (say) there’s an edge between $g_+$ and $g_-$ in $G$, it makes no difference whether there’s one between $h_+$ and $h_-$ in $H$: the new graphs $X$ and $Y$ are the same either way.

The crucial feature of the red and green men is the belt. If it wasn’t there, there’d be no guarantee that their magnitudes were equal.

By the theorem, it’s unsurprising that David got equal magnitudes for a randomly generated Whitney pair $(X, Y)$, even though it doesn’t happen for all such pairs. Indeed, suppose we do as David did and generate random graphs $G$ and $H$ by putting an edge between each pair of vertices with probability $0.4$. Then the probability that either there’s an edge between $g_+$ and $g_-$ in $G$ or there’s an edge between $h_+$ and $h_-$ in $H$ is $1 - (1 - 0.4)^2 = 0.64$. So, doing what David did will give you equal magnitudes at least $64\%$ of the time.

(I’m glad the $64\%$ chance worked out that time— otherwise we’d probably never have discovered all this.)

Why should anyone care about this result? For me, it’s not really graphs themselves that I’m primarily interested in. I care because

Graphs are a bit like convex sets.

Let me explain. A metric space $X$ is geodesic if every pair of points $x, y$ can be joined by a path of length $d(x, y)$: that is, a distance-decreasing map $[0, d(x, y)] \to X$ beginning at $x$ and ending at $y$. For instance, the geodesic subsets of $\mathbb{R}^n$ are exactly the convex sets.

Now let’s consider graphs as metric spaces. All the distances are integers, so for trivial reasons, a graph is never geodesic. But there’s something more interesting to say. Just as a metric space can be seen as a category enriched over $\mathbb{R}^+ \cup \{\infty\}$, a graph can be seen as a category enriched over $\mathbb{N} \cup \{\infty\}$. The role played for metric spaces by $[0, d]$ ($d \in \mathbb{R}^+$) is played for graphs by $[d] = \{0, 1, \ldots, d\}$ ($d \in \mathbb{N}$).

So, a category enriched over $\mathbb{N} \cup \{\infty\}$ should be called geodesic if every pair of objects $x, y$ can be joined by a path of length $d(x, y)$, where now “path” means a functor (distance-decreasing map) $[d(x, y)] \to X$ beginning at $x$ and ending at $y$. By definition of the metric on a graph, every graph is geodesic in this sense.

From the very beginning of work on the magnitude of metric spaces, there have been difficult conjectures about the magnitude of convex sets. For example, it’s believed that

$$\left|A \cup B\right| = \left|A\right| + \left|B\right| - \left|A \cap B\right|$$

whenever $A$ and $B$ are compact convex subsets of $\mathbb{R}^n$ such that $A \cup B$ is also convex. (Here $\left|\cdot\right|$ denotes magnitude.)

Despite a lot of work, we don’t seem to be close to a proof. Thus, anything that might provide a clue is welcome. Maybe proving results about the magnitude of graphs will suggest ways to prove analogous results on convex sets.

We need to be cautious, though. The inclusion-exclusion formula does not hold under the hypotheses of the Whitney twist theorem above. That is, $\left|X\right|$ and $\left|Y\right|$ are equal, but they’re not in general equal to $\left|G\right| + \left|H\right| - \left|G \cap H\right|$. Simon mentioned a counterexample: simply glue two 3-cycles together along an edge.

So is it a bad analogy? No; it’s just that there are several ways to generalize the notion of convexity from subsets of Euclidean space to metric spaces in general. For instance, instead of asking that between each pair of points there exists a geodesic, you might ask that between each pair of points there exists a unique geodesic. For subsets of $\mathbb{R}^n$, both conditions are equivalent to convexity, but for more general metric spaces, one is stricter than the other.

As Mark pointed out, trees always satisfy the analogous condition for graphs. In other words, given vertices $x$ and $y$ of a tree, distance $n$ apart, there is a unique sequence $(x_0, \ldots, x_n)$ of vertices such that $x_0 = x$, $x_n = y$, and each $x_i$ is joined by an edge to $x_{i + 1}$. And indeed, whenever a tree is the union of subtrees $A$ and $B$, we do have

$$\left| A \cup B \right| = \left|A\right| + \left|B\right| - \left|A \cap B\right|.$$

This suggests that as far as magnitude is concerned,

Trees are like convex sets

(more so than graphs are). Unfortunately, the proof of the inclusion-exclusion formula for trees is so simple that it’s unlikely to help prove anything about the magnitude of convex sets.

The proof of the Whitney twist theorem for graphs is more involved. I have very little idea how it might be used to advance our understanding of magnitude of convex sets, if indeed it can be. It’s not a conceptual or beautiful proof; it’s just a computation. It also doesn’t reveal what the common magnitude of the new graphs $X$ and $Y$ is, in terms of the old graphs $G$ and $H$.

The details  I’ll finish with a quick summary of the proof, intended only for the seriously interested.

Sticking with the notation above, we start with $(G, g_+, g_-)$ and $(H, h_+, h_-)$ and make new graphs $X$ and $Y$, differing by a Whitney twist. We assume there’s an edge between $g_+$ and $g_-$ in $G$, and also one between $h_+$ and $h_-$ in $H$. Let $w_X$ be the unique weighting on $X$. We’re going to define a weighting $w_Y$ on $Y$.

Except at the two gluing points, it’s equal to $w_X$. To define $w_Y$ at those two points, we need some notation. Divide the set of vertices of $G$ into three parts, as follows:

$$\begin{aligned} G_+ &= \{ g \in G \colon d(g_+, g) \lt d(g_-, g) \}, \\ G_0 &= \{ g \in G \colon d(g_+, g) = d(g_-, g) \}, \\ G_- &= \{ g \in G \colon d(g_+, g) \gt d(g_-, g) \}. \end{aligned}$$

The important thing to notice is that $d(g_+, g)$ and $d(g_-, g)$ can differ by at most $1$, because of the edge between $g_+$ and $g_-$. We’ve just carved $G$ up according to whether the difference is $+1$, $0$ or $-1$. Of course, we can do the same for $H$, giving sets $H_+$, $H_0$ and $H_-$.

The weighting $w_Y$ is given at the gluing point $g_+ = h_-$ of $Y$ by

$$\begin{aligned} w_Y(g_+) = w_Y(h_-) & = w_X(g_+) + \sum_{g \in G_-} q^{d(g_-, g)} w_X(g) - \sum_{g \in G_+} q^{d(g_+, g)} w_X(g) \\ &= w_X(h_-) + \sum_{h \in H_+} q^{d(h_+, h)} w_X(h) - \sum_{h \in H_-} q^{d(h_-, h)} w_X(h). \end{aligned}$$

Here the first two equalities are by definition, but the last is a lemma, which had better be true in order that the symmetry of the situation is maintained. (Its proof uses the idea of a metric space projecting to a subspace.) There are similar formulas for $w_Y(g_-) = w_Y(h_+)$.

It’s not hard to check that this $w_Y$ is a weighting. From the construction of $w_Y$ in terms of $w_X$, it’s then immediate that $\left|X\right| = \left|Y\right|$.