July 7, 2013

Whitney Twists

Posted by Tom Leinster

I’m sitting on a plane to Sydney for Category Theory 2013, the major annual gathering of category theorists. At some point I’ll write about the talk I’m giving, which answers the question about ultraproducts posed here and here. But today I’m going to tell you why these two graphs have the same magnitude:

The magnitude of a graph $G$ is a somewhat mysterious rational function associated to $G$. It was the subject of vigorous discussion back here, largely provoked by David Speyer and Simon Willerton. I’ll repeat the definition.

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|$.

Posted at July 7, 2013 7:14 AM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2630

Re: Whitney Twists

Trees are like convex sets (more so than graphs are).

One way in which this is so is that, like subsets of Euclidean space, trees are of negative type; a slightly stronger statement is that they embed isometrically in $L_1$. I wonder if inclusion-exlusion holds for magnitude of graphs which are of negative type or which embed in $L_1$.

Posted by: Mark Meckes on July 7, 2013 6:40 PM | Permalink | Reply to this

Re: Whitney Twists

No, I guess not. Simon’s example of two three-cycles glued across an edge has only four vertices, and every metric space with four points embeds in $L_1$ (even in $\R^2$ with the $\ell_1$ norm).

Posted by: Mark Meckes on July 7, 2013 6:53 PM | Permalink | Reply to this

Re: Whitney Twists

Sorry, this post was riddled with small errors. It was finished in a busy cafe and a hurry. I hope I’ve fixed everything now.

Posted by: Tom Leinster on July 8, 2013 2:24 AM | Permalink | Reply to this

Re: Whitney Twists

I was mystified when in my email I received word of a trackback to this post. The trackback went to my 2008 post on the magnitude of metric spaces.

My post??? Oh—I was posting a ‘guest post’ by someone named Tom Leinster!

That seems like ages ago, not just 2008.

Posted by: John Baez on July 8, 2013 6:44 AM | Permalink | Reply to this

Re: Whitney Twists

Yes, seems like a bygone era: when we called magnitude “cardinality” and dinosaurs walked the earth.

Posted by: Tom Leinster on July 8, 2013 8:03 AM | Permalink | Reply to this

Re: Whitney Twists

Nice. Here’s a couple of questions. Firstly, how did you figure out this weighting on $Y$? Secondly, do you know how the weightings on $X$ and $Y$ come from those on $G$ and $H$?

Posted by: Simon Willerton on July 8, 2013 8:33 AM | Permalink | Reply to this

Re: Whitney Twists

To answer my first question, I suspect if I were to have done this I would have done some examples and observed that the weights away from the glueing points are the same on $X$ and $Y$ (I think we did that [last time](http://golem.ph.utexas.edu/category/2013/04/tutte_polynomials_and_magnitud.html#c043814)), and then just tried to solve the weight equation on $Y$ using that observation and the fact that the weight equation is satisfied on $X$. Some rather inspired guess work might have been needed at the end.

One thing I’d like to clarify. Do you want $g_+\in G_+$? According to what you’ve written you do, but according to my calculation I don’t.

Posted by: Simon Willerton on July 8, 2013 10:13 PM | Permalink | Reply to this

Re: Whitney Twists

In answer to your first question: it’s as you imagined, except that no inspiration was required. Since $w_X$ and $w_Y$ were expected to agree except at the gluing points, and since the total $X$-weight of the two gluing points was supposed to be equal to the total $Y$-weight, there was only one degree of freedom—one quantity to be discovered. Discovering it was just a matter of doing the calculations and seeing what it had to be. The only significant step was proving the last equality in the last display in my post.

I don’t have a conceptual explanation of the formulas.

Yes, the definition of $G_+$ says what I wanted it to say. In particular, $g_+ \in G_+$.

Secondly, do you know how the weightings on $X$ and $Y$ come from those on $G$ and $H$?

No.

Posted by: Tom Leinster on July 9, 2013 2:19 AM | Permalink | Reply to this

Re: Whitney Twists

Thanks for the clarification. I found the error in my calculation.

Posted by: Simon Willerton on July 9, 2013 8:34 AM | Permalink | Reply to this

Post a New Comment