Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

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:

Two graphs differing by a Whitney twist

The magnitude of a graph GG is a somewhat mysterious rational function associated to GG. 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 GG, 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 GZ_G over (q)\mathbb{Q}(q), the field of rational functions in a formal variable qq. The rows and columns are indexed by the vertices of GG, and for vertices xx and yy, the (x,y)(x, y)-entry of Z GZ_G is q d(x,y)q^{d(x, y)} (understood to be 00 if d(x,y)=d(x, y) = \infty).

It’s easy to see that the element det(Z G)det(Z_G) of (q)\mathbb{Q}(q) is nonzero. (Consider q=0q = 0.) Hence Z GZ_G is invertible over (q)\mathbb{Q}(q). The magnitude of GG is the sum of all the entries of Z G 1Z_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 GG, equipped with a pair of distinguished, distinct vertices, g +g_+ and g g_-. And suppose we also have another such, (H,h +,h )(H, h_+, h_-). We can make a new graph by gluing GG to HH along the two basepoints (deleting the duplicate edge if one is created). In fact, we can do this in two ways:

  • by gluing g +g_+ to h +h_+ and g g_- to h h_-, we make a new graph XX;

  • by gluing g +g_+ to h h_- and g g_- to h +h_+, we make a new graph YY.

The graphs XX and YY are said to differ by a Whitney twist. For instance, these two graphs differ by a Whitney twist:

Two graphs differing by a Whitney twist

In case you can’t see the difference between red and green, the graph GG is the part from the belt downwards, and the graph HH is the part from the belt upwards. Since there is a belt, either GG has an edge between its two basepoints, or HH 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 GG and HH. It was.

The magnitudes of David’s graphs XX and YY 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

no edge between the gluing points

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 GG be a graph, and let g +g_+ and g g_- be vertices of GG joined by an edge. Let HH be a graph, and let h +h_+ and h h_- be vertices of HH joined by an edge. Then the two graphs

X=(G⨿H)/(g +=h +,g =h ),Y=(G⨿H)/(g +=h ,g =h +) 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 XX
  • either there is an edge between g +g_+ and g g_- in GG or there is an edge between h +h_+ and h h_- in HH
  • there’s an edge between the two gluing points of YY.

Moreover, if (say) there’s an edge between g +g_+ and g g_- in GG, it makes no difference whether there’s one between h +h_+ and h h_- in HH: the new graphs XX and YY 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)(X, Y), even though it doesn’t happen for all such pairs. Indeed, suppose we do as David did and generate random graphs GG and HH by putting an edge between each pair of vertices with probability 0.40.4. Then the probability that either there’s an edge between g +g_+ and g g_- in GG or there’s an edge between h +h_+ and h h_- in HH is 1(10.4) 2=0.641 - (1 - 0.4)^2 = 0.64. So, doing what David did will give you equal magnitudes at least 64%64\% of the time.

(I’m glad the 64%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 XX is geodesic if every pair of points x,yx, y can be joined by a path of length d(x,y)d(x, y): that is, a distance-decreasing map [0,d(x,y)]X[0, d(x, y)] \to X beginning at xx and ending at yy. For instance, the geodesic subsets of n\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][0, d] (d +d \in \mathbb{R}^+) is played for graphs by [d]={0,1,,d}[d] = \{0, 1, \ldots, d\} (dd \in \mathbb{N}).

So, a category enriched over {}\mathbb{N} \cup \{\infty\} should be called geodesic if every pair of objects x,yx, y can be joined by a path of length d(x,y)d(x, y), where now “path” means a functor (distance-decreasing map) [d(x,y)]X[d(x, y)] \to X beginning at xx and ending at yy. 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

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

whenever AA and BB are compact convex subsets of n\mathbb{R}^n such that ABA \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, |X|\left|X\right| and |Y|\left|Y\right| are equal, but they’re not in general equal to |G|+|H||GH|\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 n\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 xx and yy of a tree, distance nn apart, there is a unique sequence (x 0,,x n)(x_0, \ldots, x_n) of vertices such that x 0=xx_0 = x, x n=yx_n = y, and each x ix_i is joined by an edge to x i+1x_{i + 1}. And indeed, whenever a tree is the union of subtrees AA and BB, we do have

|AB|=|A|+|B||AB|. \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 XX and YY is, in terms of the old graphs GG and HH.

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 )(G, g_+, g_-) and (H,h +,h )(H, h_+, h_-) and make new graphs XX and YY, differing by a Whitney twist. We assume there’s an edge between g +g_+ and g g_- in GG, and also one between h +h_+ and h h_- in HH. Let w Xw_X be the unique weighting on XX. We’re going to define a weighting w Yw_Y on YY.

Except at the two gluing points, it’s equal to w Xw_X. To define w Yw_Y at those two points, we need some notation. Divide the set of vertices of GG into three parts, as follows:

G + ={gG:d(g +,g)<d(g ,g)}, G 0 ={gG:d(g +,g)=d(g ,g)}, G ={gG:d(g +,g)>d(g ,g)}. \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)d(g_+, g) and d(g ,g)d(g_-, g) can differ by at most 11, because of the edge between g +g_+ and g g_-. We’ve just carved GG up according to whether the difference is +1+1, 00 or 1-1. Of course, we can do the same for HH, giving sets H +H_+, H 0H_0 and H H_-.

The weighting w Yw_Y is given at the gluing point g +=h g_+ = h_- of YY by

w Y(g +)=w Y(h ) =w X(g +)+ gG q d(g ,g)w X(g) gG +q d(g +,g)w X(g) =w X(h )+ hH +q d(h +,h)w X(h) hH q d(h ,h)w X(h). \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 +)w_Y(g_-) = w_Y(h_+).

It’s not hard to check that this w Yw_Y is a weighting. From the construction of w Yw_Y in terms of w Xw_X, it’s then immediate that |X|=|Y|\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

9 Comments & 0 Trackbacks

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 1L_1. I wonder if inclusion-exlusion holds for magnitude of graphs which are of negative type or which embed in L 1L_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 1L_1 (even in R 2\R^2 with the 1\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 YY? Secondly, do you know how the weightings on XX and YY come from those on GG and HH?

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 XX and YY (I think we did that last time), and then just tried to solve the weight equation on YY using that observation and the fact that the weight equation is satisfied on XX. Some rather inspired guess work might have been needed at the end.

One thing I’d like to clarify. Do you want g +G +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 Xw_X and w Yw_Y were expected to agree except at the gluing points, and since the total XX-weight of the two gluing points was supposed to be equal to the total YY-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 +G_+ says what I wanted it to say. In particular, g +G +g_+ \in G_+.

Secondly, do you know how the weightings on XX and YY come from those on GG and HH?

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