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.

April 16, 2013

Tutte Polynomials and Magnitude Functions

Posted by Tom Leinster

Last summer in Barcelona, Joachim Kock floated the idea that there might be a connection between two invariants of graphs: the Tutte polynomial and the magnitude function. Here I’ll explain what these two invariants are, I’ll give you some examples, and I’ll ask for your help in understanding what the magnitude function tells us.

The Tutte polynomial of a graph is old and well-understood. It turns a graph GG into a polynomial T GT_G in two variables, with natural number coefficients: T G(x,y)[x,y]. T_G(x, y) \in \mathbb{N}[x, y]. The magnitude function of a graph is new and ill-understood. It turns a graph GG into a rational function μ G\mu_G in one variable, with rational coefficients: μ G(q)(q). \mu_G(q) \in \mathbb{Q}(q). It can also be expanded as a power series with integer coefficients: μ G(q)[[q]]. \mu_G(q) \in \mathbb{Z}[[q]]. I can’t figure out what the relationship between the two is — if any — or what information is contained in the magnitude function. It’s exasperating! I’ll be very pleased if someone can shed light on the situation.

In this post, “graphs” are always going to be finite and undirected. But some of the time I’ll allow loops and multiple edges, and some of the time I won’t. I’ll say which I’m doing.

(Formally, a graph with loops and multiple edges consists of a finite set VV, a finite set EE, and a map E(V×V)/S 2E \to (V \times V)/S_2. Here (V×V)/S 2(V \times V)/S_2 is the quotient of V×VV \times V by the obvious action of the group S 2S_2 of order 22; it can be seen as the set of subsets of VV of cardinality 1 or 2. A graph without loops or multiple edges consists of a finite set VV and a subset EV×VE \subseteq V \times V that, seen as a relation on VV, is symmetric and irreflexive.)

The Tutte polynomial

The Tutte polynomial knows a lot about a graph. It knows how many edges the graph has, how many maximal forests it contains, and how many ways there are to colour each of its vertices from a palette of 38 colours without ever giving the same colour to adjacent vertices. It’s related to the Potts model in statistical physics and the Jones polynomial of knot theory.

I’ll give you the definition in a moment, but first we need some terminology.

For this part, graphs will be allowed to have loops and multiple edges. Given an edge ee of a graph GG, there are two fundamental operations we can perform:

  • Deletion. The graph GeG - e is simply GG with the edge ee removed (but the vertices left untouched).

  • Contraction. The graph G/eG/e is formed from GG by first removing ee, then identifying the two vertices that it used to join.

An edge ee is called a bridge if GeG - e has more connected-components than GG, and a loop if it joins a vertex to itself.

The Tutte polynomial T G(x,y)[x,y]T_G(x, y) \in \mathbb{N}[x, y] of a graph GG is characterized by the following two conditions:

  • T G=T Ge+T G/eT_G = T_{G - e} + T_{G/e} if ee is neither a bridge nor a loop;

  • T G(x,y)=x by T_G(x, y) = x^b y^\ell if GG consists of bb bridges, \ell loops, and no other edges.

It takes some work to prove that there’s any polynomial with these two properties, since in the first condition there are usually many different edges ee we could choose. But this form of the definition has the advantage that it provides a nice algorithm for calculating Tutte polynomials. For instance, here’s a picture from Wikipedia of the algorithm at work:

Tutte polynomial algorithm

The conclusion is that if GG is the five-vertex graph at the top of the tree then T G(x,y)=x 3+2x 2+y 2+2xy+x+y. T_G(x, y) = x^3 + 2x^2 + y^2 + 2x y + x + y.  

The magnitude function

I’ll say twice what the magnitude function of a graph is: once for people who know what the magnitude of a metric space is, and once for people who don’t. In this part, graphs are not allowed to have loops or multiple edges — or more exactly, they could do, but adjoining or deleting loops or duplicate edges doesn’t make any difference to the magnitude function.

First, here’s the explanation for if you know about magnitude of metric spaces. Every finite metric space AA has a magnitude function t|tA|t \mapsto \left|t A\right|, where tAt A is AA scaled up by a factor of tt and the bars indicate magnitude. (This “function” may have a finite number of singularities.) We can turn a graph GG into a metric space by taking the points to be the vertices and the distance between two vertices to be the number of edges in a shortest path joining them. The magnitude function of a graph is the magnitude function of the resulting metric space. It will be convenient to make the substitution q=e tq = e^{-t} and write μ G(q)=|tG|\mu_G(q) = \left|t G\right|.

Now here’s a direct explanation.

List the vertices in some order: v 1,,v nv_1, \ldots, v_n. (The choice of order won’t affect anything.) Let d ijd_{i j} be the number of edges in a shortest path from v iv_i to v jv_j (assuming there is one). Let Z G(q)Z_G(q) be the square matrix over [q]\mathbb{Q} [q] whose (i,j)(i, j)-entry is q d ijq^{d_{i j}}, or 00 if there is no path from v iv_i to v jv_j.

We’re going to want to invert Z G(q)Z_G(q), so let’s consider its determinant. It’s a polynomial in qq. Also, Z G(0)=IZ_G(0) = I, so detZ G(0)=1\det Z_G(0) = 1; hence detZ G(q)\det Z_G(q) is not the zero polynomial. It follows that the matrix Z G(q)Z_G(q) is invertible over (q)\mathbb{Q}(q), the field of rational functions with rational coefficients. We define

μ G(q)(q) \mu_G(q) \in \mathbb{Q}(q)

to be the sum of all n 2n^2 entries of the inverse matrix Z G(q) 1Z_G(q)^{-1}. This is the magnitude function of the graph GG.

It’s a fact that the magnitude function of a graph can always be expanded as a power series with integer coefficients. This is a special property of μ G\mu_G: your average rational function over \mathbb{Q} is merely a Laurent series with rational coefficients.

(The key to the proof is that the constant term of the polynomial detZ G(q)\det Z_G(q) is 11, which is invertible in \mathbb{Z}. It follows that 1/detZ G(q)1/\det Z_G(q) can be expanded as a power series over \mathbb{Z}. Hence μ G(q)\mu_G(q) can be too.)

What does the magnitude function tell us about a graph?

I’ll come clean: I have no direct evidence that the magnitude function of a graph tells us anything interesting about it. However, in several other settings, magnitude and related invariants have proven to be very fruitful, producing important quantities associated to topological spaces, metric spaces, sets, groupoids, orbifolds, associative algebras, etc. So it’s a good bet that it’s going to be fruitful for graphs too.

Moreover, in the particularly interesting setting of metric spaces, magnitude has been particularly reluctant to give up its secrets. So, the lack of obvious interpretation for the magnitude function of a graph doesn’t make me think it’s less likely to be interesting: it makes me wonder what it’s hiding!

But what does the magnitude function tell us? It’s hard to see. For instance, take the 4-cycle C 4C_4:

4-cycle

We have

μ C 4(q)=4(1+q) 2=48q+12q 216q 3+. \mu_{C_4}(q) = \frac{4}{(1 + q)^2} = 4 - 8q + 12q^2 - 16q^3 + \cdots.

How can we interpret this? It’s tempting to try to understand a power series over \mathbb{Z} as the generating function of something, but what? Even ignoring the negative signs, what’s being counted here?

For another example, take GG to be a forest with vertex-set VV and edge-set EE. Then

μ G(q) =|π 0(G)|+|E|1q1+q =|V|2|E|q+2|E|q 22|E|q 3+,\begin{aligned} \mu_G(q) &= \left|\pi_0(G)\right| + \left|E\right| \frac{1 - q}{1 + q}\\ &= \left|V\right| - 2\left|E\right|q + 2\left|E\right|q^2 - 2\left|E\right|q^3 + \cdots, \end{aligned}

where π 0(G)\pi_0(G) is the set of connected-components of GG. What is this function telling us about the graph?

Tutte vs. magnitude

In some ways, the information contained in the magnitude function seems to be complementary to that contained in the Tutte polynomial. For example:

  • the magnitude function knows how many vertices a graph has, but the Tutte polynomial doesn’t (at least if we’re allowing disconnected graphs)

  • the Tutte polynomial knows how many edges a graph has, but the magnitude function doesn’t (at least if we’re allowing multiple edges).

In other ways, the magnitude function and the Tutte polynomial seem more similar than complementary. Let’s consider some families of graphs known to have the same Tutte polynomial:

  • all trees with a given number of edges have the same Tutte polynomial; they also have the same magnitude function.

  • The three graphs known as the bull, the (3,2)-tadpole and the cricket (shown below) all have the same Tutte polynomial; they also all have the same magnitude function.

In fact, it’s consistent with the evidence below that for connected graphs, the Tutte polynomial determines the magnitude function.

However, in examples such as those above, I see no way of transforming the Tutte polynomial into the magnitude function. One way of proving that such a transformation exists would be to use the so-called “universal property” of the Tutte polynomial. (I don’t know whether it’s a universal property in the categorical sense.) Roughly, this says that Tutte determines magnitude if μ G\mu_G is determined by μ Ge\mu_{G-e} and μ G/e\mu_{G/e} whenever ee is an edge of GG that is neither a bridge nor a loop. But I don’t know whether that’s the case; I suspect not.

All in all, I don’t think the magnitude function is likely to be a specialization of the Tutte polynomial, even for connected graphs. In other words, the magnitude function seems to contain extra information about the graph that Tutte doesn’t. But what?

Properties and examples

I’ll now try to convey an idea of how the magnitude function behaves, by way of some basic properties and examples. For comparison, I’ll show the behaviour of the Tutte polynomial alongside.

  1. Disjoint unions Any two graphs GG and HH have a disjoint union G+HG + H.

    Tutte: T G+H=T GT HT_{G + H} = T_G T_H.

    Magnitude: μ G+H=μ G+μ H\mu_{G + H} = \mu_G + \mu_H.

  2. Joins Suppose we have a graph GG with a distinguished vertex xx, and another graph HH with a distinguished vertex yy. We can form a new graph G*HG * H, the “join”, by first taking G+HG + H then identifying xx with yy.

    Tutte: T G*H=T GT HT_{G * H} = T_G T_H.

    Magnitude: μ G*H=μ G+μ H1\mu_{G * H} = \mu_G + \mu_H - 1.

  3. Knows the number of vertices?

    Tutte: no, if we’re allowing graphs to have multiple connected-components: see “discrete graphs” below. Yes, if we stick to connected graphs: then the degree of T G(x,y)T_G(x, y) as a polynomial in xx (with yy regarded as constant) is |V|1\left|V\right| - 1.

    Magnitude: yes: it’s μ G(0)\mu_G(0).

  4. Knows the number of edges?

    Tutte: yes: T G(2,2)=2 |E|T_G(2, 2) = 2^{\left|E\right|}. (Here and later, I’ll use EE for the set of edges of a graph GG, and VV for the set of vertices.)

    Magnitude: no, if we’re allowing loops or multiple edges, since adding a loop or a duplicate edge doesn’t change the magnitude. Yes, if we stick to graphs without loops or multiple edges: the coefficient of qq in the power series expansion of μ G(q)\mu_G(q) is 2-2 times the number of edges. In other words, |E|=μ G(0)/2\left|E\right| = -\mu'_G(0)/2. (See this comment, and the reply to it, below.)

  5. Discrete graphs Let GG be a discrete graph, that is, one with no edges at all.

    Tutte: T G(x,y)=1T_G(x, y) = 1.

    Magnitude: μ G(q)=|V|\mu_G(q) = \left|V\right|.

  6. Forests Let GG be a forest, that is, a disjoint union of trees.

    Tutte: T G(x,y)=x |E|T_G(x, y) = x^{\left|E\right|}.

    Magnitude: μ G(q)=|π 0(G)|+|E|1q1+q=|V|2|E|q+2|E|q 22|E|q 3+\mu_G(q) = \left|\pi_0(G)\right| + \left|E\right|\cdot \frac{1-q}{1 + q} = \left|V\right| - 2\left|E\right|q + 2\left|E\right|q^2 - 2\left|E\right|q^3 + \cdots.

  7. Cycles Let C nC_n be the nn-cycle:

    n-cycle

    Tutte: T C n(x,y)=x n1+x n2++x+y=x nxx1+yT_{C_n}(x, y) = x^{n-1} + x^{n-2} + \cdots + x + y = \frac{x^n - x}{x - 1} + y

    Magnitude: μ C n(q)=n(q1)q (n+1)/2+q (n+1)/2q1\mu_{C_n}(q) = \frac{n(q - 1)}{q^{\lfloor (n+1)/2 \rfloor} + q^{\lceil (n+1)/2 \rceil} - q - 1}. (Those are the floor and ceiling functions in the denominator.) This naturally splits into two cases. If nn is even then μ C n(q)=n(q1)(q n/21)(q+1). \mu_{C_n}(q) = \frac{n(q - 1)}{(q^{n/2} - 1)(q + 1)}. If nn is odd then μ C n(q)=n(q1)2q (n+1)/2q1. \mu_{C_n}(q) = \frac{n(q - 1)}{2q^{(n+1)/2} - q - 1}.

  8. Complete graphs Let K nK_n be the complete graph on nn vertices (that is, every vertex is joined to every other by a single edge).

    Tutte: it seems that there is no neat formula for T K nT_{K_n}, and that computing it is nontrivial. A single example: T K 4(x,y)=(x 3+y 3)+(x 2+y 2)+2(x+y) 2+2(x+y). T_{K_4}(x, y) = (x^3 + y^3) + (x^2 + y^2) + 2(x + y)^2 + 2(x + y).

    Magnitude: μ K n(q)=n1+(n1)q\mu_{K_n}(q) = \frac{n}{1 + (n - 1)q}.

  9. Complete bipartite graphs I’ll just do one. Let K 2,3K_{2, 3} be this graph:

    Complete bipartite graph 2, 3

    Tutte: T K 2,3(x,y)=x 4+2x 3+3x 2+3xy+y 2+x+yT_{K_{2,3}}(x, y) = x^4 + 2x^3 + 3x^2 + 3x y + y^2 + x + y.

    Magnitude: μ K 2,3(q)=57q(1+q)(12q 2)=512q+22q 236q 3+56q 4\mu_{K_{2,3}}(q) = \frac{5 - 7q}{(1 + q)(1 - 2q^2)} = 5 - 12q + 22q^2 - 36q^3 + 56q^4 - \cdots.

  10. Bull, tadpole, cricket These three graphs all have the same Tutte polynomial and the same magnitude function:

    Bull graph     Tadpole graph     Cricket graph

    Let GG be any one of them.

    Tutte: T G(x,y)=x 2(x 2+x+y)T_G(x, y) = x^2(x^2 + x + y).

    Magnitude: μ G(q)=5+5q4q 2(1+q)(1+2q)=510q+16q 228q 3+52q 4\mu_G(q) = \frac{5 + 5q - 4q^2}{(1 + q)(1 + 2q)} = 5 - 10q + 16q^2 - 28q^3 + 52q^4 - \cdots.

    There’s no mystery as to why they all have the same Tutte polynomial. It’s simply because all three graphs are the join of C 3C_3 and two copies of the graph consisting of a single edge, and the Tutte polynomial of the join of a bunch of graphs is determined by their individual Tutte polynomials. The same goes for the magnitude functions.

  11. Petersen graph Don Knuth observed that the Petersen graph “serves as a counterexample to many optimistic predictions about what might be true for graphs in general”. So even though I don’t have a prediction to be counterexampled, I thought I’d better check its magnitude function for disturbing behaviour. I’m not disturbed.

    Petersen graph

    Tutte: according to Wikipedia, the Petersen graph PP has Tutte polynomial T P(x,y)= 36x+120x 2+180x 3+170x 4+114x 5+56x 6+21x 7+6x 8+x 9 +36y+84y 2+75y 3+35y 4+9y 5+y 6+168xy+240x 2y+170x 3y+70x 4y +12x 5y+171xy 2+105x 2y 2+30x 3y 2+65xy 3+15x 2y 3+10xy 4.\begin{aligned} T_P(x, y) =& 36 x + 120 x^2 + 180 x^3 + 170x^4+114x^5 + 56x^6 +21 x^7 + 6x^8 + x^9\\ &+ 36y +84 y^2 + 75 y^3 +35 y^4 + 9y^5+y^6 + 168x y + 240x^2 y +170x^3 y +70 x^4 y\\ & + 12x^5 y + 171x y^2+105 x^2 y^2 + 30x^3 y^2 + 65x y^3 +15x^2 y^3 +10x y^4. \end{aligned}

    Magnitude: μ P(q)=101+3q+6q 2=1030q+30q 2+90q 3450q 4+\mu_P(q) = \frac{10}{1 + 3q + 6q^2} = 10 - 30q + 30q^2 + 90q^3 - 450q^4 + \cdots.

    Actually, this does defeat a conjecture! Having read the previous examples, you might have wondered whether the coefficients of the magnitude function (when expanded as a power series) always alternate in sign. The Petersen graph shows that they don’t.

  12. Linear codes I’m going to be very sketchy here. (If you want to know more, just say so in the comments.) Let FF be a finite field. A linear code over FF is simply a linear subspace of F nF^n, for some nn.

    Tutte: Every linear code CC has a Tutte polynomial T CT_C. (More exactly, the definition of Tutte polynomial extends smoothly from graphs to matroids, and every linear code gives rise to a matroid.) But also, with every linear code is associated an important polynomial called its “weight enumerator”. It’s a fact that the weight enumerator of a code CC is determined by its Tutte polynomial together with the cardinalities of CC and F nF^n.

    Magnitude: On the other hand, every linear code can be regarded as a metric space (with the Hamming distance inherited from F nF^n), and so has a magnitude function. It’s a fact that the weight enumerator of a code is essentially the same thing as its magnitude function; each determines the other once you know the cardinality of CC.

    So in the case of linear codes, the Tutte polynomial (plus the cardinalities of CC and F nF^n) determines the magnitude function.

Questions

The magnitude function of a graph remains mysterious to me. I have very little intuition for what it means. I understand the magnitude of a metric space moderately well for subspaces of n\mathbb{R}^n, but metric spaces coming from graphs are about as un-Euclidean as can be.

Here are some questions I’d like answering.

  1. What information can be read off from the magnitude function of a graph?

  2. Is there a useful way to regard the power series expansion of the magnitude function as a generating function? In other words, do the coefficients count something?

  3. It’s consistent with the evidence above that two graphs with the same Tutte polynomial and the same number of vertices have the same magnitude function. Is it true?

  4. It’s consistent with the evidence above that two connected graphs with the same Tutte polynomial have the same magnitude function. Is it true?

Posted at April 16, 2013 9:45 PM UTC

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

62 Comments & 2 Trackbacks

Re: Tutte Polynomials and Magnitude Functions

It occurs to me belatedly that in all the examples I’ve given, the coefficient of qq in the power series expansion of μ G(q)\mu_G(q) is 2-2 times the number of edges.

Posted by: Tom Leinster on April 17, 2013 1:20 AM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

OK, it’s true in general. There’s a bit of faffing over which rings everything lives in, but essentially one can prove this by “setting q 2=0q^2 = 0” and calculating the magnitude function of a graph under that assumption. It comes out as |V|2|E|q\left|V\right| - 2\left|E\right|q, for a graph G=(V,E)G = (V, E).

In a bit more detail: a weighting on a matrix ZZ is a column vector ww such that ZwZ w is the vector consisting entirely of 11s. If ZZ is invertible then there’s a unique weighting ww, and the sum of the entries of ww is equal to the sum of all the entries of Z 1Z^{-1}. So, we can find the magnitude function of GG by finding a weighting on Z G(q)Z_G(q) and then summing its entries.

As usual, the rows and columsn of Z G(q)Z_G(q) are indexed by the vertices of GG. Since we’ve declared q 2q^2 to be 00, its entries are rather simple: it has 11s down the diagonal, a qq in every entry corresponding to an edge, and 00s everywhere else. It’s easy to show that there’s a weighting ww given by

w x=1deg(x)q w_x = 1 - deg(x)q

for each vertex xx, where deg(x)deg(x) is the degree or valency of xx. Hence the magnitude function — still under the assumption that q 2=0q^2 = 0 — is

xV(1deg(x)q)=|V|2|E|q. \sum_{x \in V} (1 - deg(x) q) = \left|V\right| - 2\left|E\right|q.

By an argument I’m not making explicit, it follows that this is the beginning of the power series expansion of the actual magnitude function.

Since no one else has commented so far, I’ll go back and add this information to the main post now.

Posted by: Tom Leinster on April 17, 2013 2:38 AM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

Cool stuff! I’m trying to track down what the coefficient of q 2q^2 is counting in case GG has no loops or multiple edges. In detZ G(q)det Z_G(q), the qq-coefficient is always zero, and the q 2q^2-coefficient is E-E, so the inverse determinant modulo q 3q^3 is 1+Eq 21+E q^2. And in Z G(q)Z_G(q)’s cofactor matrix, there seems to be a q 2-q^2 for every pair of non-incident edge and vertex, a +q 2+q^2 for every pair of edges sharing one vertex, and a q 2-q^2 for each pair of vertices a distance of 22 apart. These last two coefficients may be counted as 6 times the number of triangles Δ\Delta, plus 2 times the number of “redundant wedges” Λ\Lambda', where a “wedge” is an induced subgraph in the shape of a triangle with a missing edge, and the number of redundant wedges is the number of wedges minus the number of distinct pairs of vertices that appear as the “horns” of wedges (i.e. the number of minimal distances of length 2). So for a grand total, working modulo q 3q^3 we have

μ G(q)=(1+Eq 2)(V2Eq+(E(V2)+6Δ+2Λ)q 2)\mu_G(q) = (1+E q^2)(V - 2E q + (-E(V-2) + 6\Delta + 2\Lambda')q^2)

μ G(q)=V2Eq+(2E+6Δ+2Λ)q 2\mu_G(q) = V - 2E q + (2 E + 6\Delta + 2\Lambda')q^2,

where Δ\Delta is the number of triangles of GG and Λ\Lambda' is the number of redundant wedges.

It’s late here and I’m not sure I’ve calculated entirely correctly in the general case, but this seems to agree with your formulas for

forests (Δ=Λ=0\Delta=\Lambda'=0),

3-cycles (Δ=1,Λ=0\Delta=1, \Lambda'=0),

4-cycles (Δ=0,Λ=2\Delta=0, \Lambda'=2),

nn-cycles for n5n\geq 5 (Δ=Λ=0\Delta=\Lambda'=0),

complete graphs K nK_n (Δ=n(n1)(n2)/6,Λ=0\Delta = n(n-1)(n-2)/6, \Lambda'=0),

K 2,3K_{2,3} (Δ=0,Λ=5\Delta=0, \Lambda'=5),

and the Petersen graph (Δ=Λ=0\Delta=\Lambda'=0).

Posted by: Owen Biesel on April 17, 2013 7:12 AM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

Excellent! This would also explain the empirical observation that the coefficient of q 2q^2 is an even, nonnegative integer.

It also gives a hint on what to expect for the higher order terms. I can see two possibilities. It could be that there’s a way of re-expressing the coefficient of q 2q^2 in some neat way that neither of us is seeing at the moment, in which case we might hope to generalize that description to higher powers of qq. Or if not, we’re presumably going to get more and more complicated expressions for the higher coefficients.

I wonder whether the number of redundant wedges can be expressed in terms of the number of 4-cycles? After all, if you have vertices xx and yy distance 22 apart, and two different paths of length 22 between them, that makes a 44-cycle.

It would definitely be progress if we could express the coefficients of q nq^n as a linear combination of the numbers of cycles of given lengths. That is, writing μ G(q)= n=0 a G,nq n\mu_G(q) = \sum_{n = 0}^\infty a_{G, n} q^n, can we find rational c n,kc_{n, k} (independent of GG) such that

a G,n= kc n,k|{k-cycles in  G}|? a_{G, n} = \sum_k c_{n, k} \left| \{ k\text{-cycles in }  G \} \right|?

Or equivalently, can we find rational d n,kd_{n, k} (independent of GG) such that

a G,n= kd n,k|Hom(C k,G)|? a_{G, n} = \sum_k d_{n, k} \left| Hom(C_k, G) \right|?

Posted by: Tom Leinster on April 17, 2013 12:26 PM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

I was also hoping that the number of “redundant wedges” could be expressed in terms of the number of 44-cycles, but what dissuaded me (after wondering why my formulas worked for every one of your example graphs except K 2,3K_{2,3}) was that I had missed this fact: if you glue together nn wedges at their horns to get K 2,nK_{2,n}, the number of redundant wedges grows linearly in nn (namely, it’s 2n12n-1) and the number of 44-cycles grows quadratically (n(n1)/2n(n-1)/2). And there are problems going the other way, too: a 44-cycle only gives us wedges if it is missing its diagonals, since the wedge can’t just be a subgraph but has to be an induced (i.e. full) subgraph, a minimal path of length 2. But certainly, if there are no squares, or if every square has both diagonals, then there are no redundant wedges; this fact helped count the redundant wedges in your examples.

So, for example, K 4K_4 and K 2,3K_{2,3} both have three 44-cycles, but the former has no redundant wedges and the latter has 55. As far as I know, the number of triangles may be enough to deduce the number of redundant wedges from the number of 44-cycles and vice versa, but there’s no fixed linear relation among the three quantities (a 33-cycle has one triangle and no squares or wedges, and the number of squares and wedges are in general not proportional). Perhaps there is if you toss in vertices and edges, or if you allow the relationship to be polynomial?

Posted by: Owen Biesel on April 17, 2013 2:31 PM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

Another belated thought: consider what graph theorists call the “cartesian product\square of graphs (but isn’t the categorical product). I mentioned it just recently.

The metric space arising from GHG \square H is the 1\ell^1 product of the spaces arising from GG and HH. In other words, it’s the “product” of metric spaces you get by adding the distances in the two components. It’s a fact that the magnitude of such a product space is simply the product of the magnitudes. Hence

μ GH=μ Gμ H. \mu_{G \square H} = \mu_G \cdot \mu_H.

This explains the fact that μ C 4\mu_{C_4}, the magnitude function of the 4-cycle, is the square of a rational function. It’s because C 4=K 2K 2C_4 = K_2 \square K_2 (where K 2K_2 is the graph consisting of a single edge), and so μ C 4=μ K 2 2\mu_{C_4} = \mu_{K_2}^2.

I don’t know whether there’s a nice formula for the Tutte polynomial of GHG \square H. A quick web search didn’t turn anything up. Does anyone know?

Posted by: Tom Leinster on April 17, 2013 1:43 AM | Permalink | Reply to this
Read the post Tutte Polynomials and Magnitude Functions
Weblog: The n-Category Café
Excerpt: The magnitude function is a mysterious invariant of graphs. It's closely related to invariants that have proven meaningful and useful in other branches of mathematics. But uncovering its meaning for graphs poses a challenge.
Tracked: April 17, 2013 2:41 AM

Re: Tutte Polynomials and Magnitude Functions

Interesting stuff! I don’t have anything constructive to say, but I can illustrate the following point you made:

metric spaces coming from graphs are about as un-Euclidean as can be.

We know that the magnitude function |tX||tX| of a subset XX of Euclidean space is continuous and defined for every t(0,)t\in (0,\infty), but the following plot shows (in red) the magnitude function |tG||tG| of a random graph GG, generated by maple, with 101101 vertices and probability 0.10.1 that any two given vertices share an edge. (On the xx-axis we have tt which is logq\log q.)

Magnitude function of a random graph

The peaks represent places where the magnitude is not defined but the resolution of the picture doesn’t necessarily make that clear.

[The blue line represents the spread function of the random graph. This is continuous and everywhere defined: it is much more chilled-out than the magnitude function.]

It is interesting that you use e te^t as your fundamental variable whereas I like to plot semi-logarithmically which means I use logt\log t as my fundamental variable. I want to treat all scales the same, and you seem to be emphasizing small scales – I’m not sure if that’s a accurate portrayal of what’s really going on!

Posted by: Simon Willerton on April 17, 2013 10:35 AM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

Thanks!

Re your last paragraph, I’m thinking algebraically rather than numerically — that is, treating qq as a formal variable rather than a real number. (Incidentally, qq is e te^{-t}, not e te^t.) So it’s not that I want to emphasize one part of parameter space over another. But I agree, it’s interesting that the two priorities pull in opposite directions.

It would also be interesting to go through this whole thing for spread in place of magnitude. Mimicking the definition of μ G\mu_G in terms of magnitude, we’d define the spread function of a graph G=(V,E)G = (V, E) as

ε G(q)= xG1 yGq d(x,y) \varepsilon_G(q) = \sum_{x\in G} \frac{1}{\sum_{y \in G} q^{d(x, y)}}

where dd is the usual geodesic distance in the graph. (Maybe there should be a “00” decorating that ε\varepsilon somewhere, to emphasize that it’s what you call the zero-spread.)

By definition, ε G(q)(q)\varepsilon_G(q) \in \mathbb{Q}(q): it’s a rational function. Also, each of the terms yGq d(x,y)\sum_{y \in G} q^{d(x, y)} is a polynomial over \mathbb{Z} with constant term 11, so, just like the magnitude function, the spread function can be expanded as a power series over \mathbb{Z}. So we have

μ G(q),ε G(q)(q)[[q]]. \mu_G(q), \varepsilon_G(q) \in \mathbb{Q}(q) \cap \mathbb{Z}[[q]].

Your Theorem 3 implies that the spread function and magnitude function are equal for graphs that are homogeneous (meaning that the automorphism group acts transitively on vertices). The simplest non-homogeneous graph is this:

G=G = o—o—o

This graph is a tree, so the formulas under “Forests” above tell us that the magnitude function is

μ G(q) =1+21q1+q=3q1+q =34q+4q 24q 3+4q 4. \begin{aligned} \mu_G(q) &= 1 + 2\cdot \frac{1 - q}{1 + q} = \frac{3 - q}{1 + q}\\ &= 3 - 4q + 4q^2 - 4q^3 + 4q^4 - \cdots. \end{aligned}

The spread function is

ε G(q) =21+q+q 2+11+2q =34q+4q 26q 3+14q 432q 5+66q 6130q 7+256q 8510q 9+. \begin{aligned} \varepsilon_G(q) &= \frac{2}{1 + q + q^2} + \frac{1}{1 + 2q}\\ &= 3 - 4q + 4q^2 - 6q^3 + 14q^4 - 32q^5 + 66q^6 - 130 q^7 + 256q^8 - 510q^9 + \cdots. \end{aligned}

(The power series expansion of the spread function is just output from Sage. The coefficients appear to be the powers of 2-2 with an offset that changes with period three: +2,2,0,+2,2,0,+2, -2, 0, +2, -2, 0, \ldots.)

Can you make anything of this?

Posted by: Tom Leinster on April 17, 2013 11:16 AM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

Ah, so you’ve learnt sage? I thought that meant that I was out of job being your computer algebra monkey, but fortunately –

“Can you make something of this?”

– you need someone to interpret the output for you.

Observe that 11+2q=12q+4q 28q 3+16q 432q 5+64q 6128q 7+ \frac{1}{1+2q}=1-2 q+4 q^2-8 q^3+16 q^4-32 q^5+64 q^6-128 q^7+\dots and that 11+q+q 2=1q+q 3q 4+q 6q 7+, \frac{1}{1+q+q^2}=1-q+q^3-q^4+q^6-q^7+\dots, hence conclude that your perception about powers of 22 with an offset was correct.

Now lets think about the constant and linear term in the spread of a graph.

The spread of the graph GG is given by ϵ G(q)= x1 yq d(x,y).\epsilon_G(q)=\sum_x \frac{1}{\sum_y q^{d(x,y)}}.

So for each vertex xx we get an additive contribution of 1 yq d(x,y)=1 d=0 N d(x)q d=1N 1(x)q+O(q 2)\frac{1}{\sum_y q^{d(x,y)}}=\frac{1}{\sum_{d=0}^\infty N_d(x)q^d} = 1 - N_1(x)q +O(q^2) where N d(x)N_d(x) is the number of vertices a distance exactly dd from the vertex xx. Adding these altogether we get ϵ G(q)= x1N 1(x)q+O(q 2)=V2Eq+O(q 2),\epsilon_G(q)=\sum_x 1 - N_1(x)q +O(q^2)= V -2E q+O(q^2), providing that we don’t have any loops or multiple edges (this condition means that xN 1(x)=2E\sum_x N_1(x)=2E).

So the first two terms in the spread and the magnitude agree. From your example we see that the fourth term can differ. What about the third term – the coefficient of q 2q^2?

Posted by: Simon Willerton on April 17, 2013 2:17 PM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

Ah, so you’ve learnt sage? I thought that meant that I was out of job being your computer algebra monkey

Don’t worry, Simon, you’re still my monkey. I’ve only learnt Sage in the same sense that I’ve learnt German: it’s enough for occasional brief forays, but it’s exhausting, limited to the most basic tasks, and requires me to lean heavily on the documentation.

So the first two terms in the spread and the magnitude agree.

Nice! As for the coefficient of q 2q^2, who knows? If pessimistic, one could calculate the spread functions of all the graphs above, looking for a counterexample. If optimistic, one could attempt something like Owen’s analysis above for the spread function.

Posted by: Tom Leinster on April 17, 2013 2:36 PM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

In terms of distance-one and distance-two neighbours, the coefficient of q 2q^2 in ϵ G(q)\epsilon_G(q), the spread function of GG, is xG(N 1(x) 2N 2(x)).\sum_{x \in G}(N_1(x)^2-N_2(x)).
I haven’t figured out if this is the same as what Owen gets, but I have checked that it agrees with your calculations of the coefficient of q 2q^2 in the magnitude of K 2,3K_{2,3} and of the bull, the tadpole and the cricket (which might well have different spreads at higher order, I haven’t checked). As for the nn-cycle, the complete graph and the Petersen graph, these are all homogeneous so will have the same spread and magnitude anyway.

Posted by: Simon Willerton on April 17, 2013 5:48 PM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

According to Owen, the coefficient of q 2q^2 in the magnitude function μ G(q)\mu_G(q) is 2E+6Δ+2Λ2E+6\Delta+2\Lambda' and 6Δ+2Λ6\Delta+2\Lambda' is equal to the number of pairs of edges sharing one vertex minus the number of pairs of vertices a distance of 2 apart. If I’ve understood correctly, then we find 2E+6Δ+2Λ =2E+ x(N 1(x))(N 1(x)1) xN 2(x) =2E+ x(N 1(x) 2N 1(x)N 2(x)) =2E2E+ x(N 1(x) 2N 2(x)) = x(N 1(x) 2N 2(x)). \begin{aligned} 2E+6\Delta+2\Lambda'&=2E+ \sum_x (N_1(x))(N_1(x)-1) -\sum_x N_2(x)\\ &=2E+ \sum_x (N_1(x)^2 - N_1(x) -N_2(x))\\ &=2E -2E+\sum_x (N_1(x)^2 -N_2(x))\\ &=\sum_x (N_1(x)^2 -N_2(x)). \end{aligned}

The latter expression is the quadratic term in the spread function of the graph GG. Thus the magnitude and spread functions have the same first three terms!

Note that because of a sign error that Tom pointed out, I was wrong to say that writing in terms of qq is about looking at graphs at small scales. Rather, it can be thought of as looking at graphs at large scales: q=0q=0 corresponds to t=+t=+\infty. (I realise we are just doing things algebraically and not numerically.) We know that for a finite metric space XX we have lim t|tX|=card(X)\lim_{t\to \infty} |t X|= card(X) this is why we have μ G(0)=V\mu_G(0)=V. So the fact that the first three terms of the magnitude μ G(q)\mu_G(q) and spread ϵ G(q)\epsilon_G(q) functions coincide for a graph GG is corresponding to the fact that for sufficiently large scalings of the graph the magnitude and spread are pretty darned close. See the plot for the random graph pictured above.

Posted by: Simon Willerton on April 18, 2013 9:59 AM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

Actually, it’s not hard to write down a formula for the coefficients of the power series μ G(q)\mu_G(q). If μ G(q)= n=0 c nq n\mu_G(q) = \sum_{n = 0}^\infty c_n q^n then

c n= k=0 n(1) k n 1,,n k1:n 1++n k=n#{(x 0,,x k)|d(x 0,x 1)=n 1,,d(x k1,x k)=n k}. c_n = \sum_{k = 0}^n (-1)^k \sum_{n_1, \ldots, n_k \geq 1 \colon n_1 + \cdots + n_k = n} \# \{(x_0, \ldots, x_k) | d(x_0, x_1) = n_1, \ldots, d(x_{k - 1}, x_k) = n_k\}.

Taking n=0,1,2n = 0, 1, 2 gives the three formulas we already know.

It follows that the magnitude function of a graph is given by

μ G(q)= k=0 (1) k x 0x 1x kq d(x 0,x 1)++d(x k1,x k). \mu_G(q) = \sum_{k = 0}^\infty (-1)^k \sum_{x_0 \neq x_1 \neq \cdots \neq x_k} q^{d(x_0, x_1) + \cdots + d(x_{k - 1}, x_k)}.

This is very like a formula for the Euler characteristic of a finite category A\mathbf{A} containing no nontrivial isomorphisms or idempotents:

χ(A)= k=0 (1) k a 0a 1a k#(Hom(a 0,a 1)××Hom(a k1,a k)). \chi(\mathbf{A}) = \sum_{k = 0}^\infty (-1)^k \sum_{a_0 \neq a_1 \neq \cdots \neq a_k} \#(Hom(a_0, a_1) \times \cdots \times Hom(a_{k-1}, a_k)).

Posted by: Tom Leinster on May 3, 2013 10:27 AM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

That’s very nice. When I talk about magnitude I sometimes like to finish with some of Simon’s results on magnitude of homogeneous Riemannian manifolds and say that appearance of Euler characteristic shows that magnitude really remembers its origin as something analogous to the Euler characteristic of a space. It’s nice to see another manifestation of that.

Posted by: Mark Meckes on May 3, 2013 3:49 PM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

Here’s an example. For a graph GG we define TT (for ‘triangles’, or ‘third’) to be the common quadratic coefficient for the magnitude and graph functions.

T2E+6Δ+2Λ= xG(N 1(x) 2N 2(x)).T\coloneqq 2E+6\Delta+2\Lambda' =\sum_{x\in G} (N_1(x)^2 -N_2(x)).

Then the magnitude and spread functions (in terms of qq) both begin V2Eq+Tq 2V-2E q+T q^2. If we write q=e tq=e^{-t} then we can plot V2Ee t+Te 2tV-2 E e^{-t}+T e^{-2t} with the usual magnitude and spread functions (in terms of tt).

Here I’ve taken a random graph with 101101 vertices (generated with probability 0.10.1 that two vertices share an edge) and plotted magnitude in red, spread in blue, and the “common quadratic approximation” V2Ee t+Te 2tV-2 E e^{-t}+T e^{-2t} in green. For comparison I plotted the “common linear approximation” V2Ee tV-2 E e^{-t} in brown.

plot of a random graph

I’m sure you’ll agree that the green curve a nice approximation to both functions once all of the crazy behaviour of the magnitude function is out of the way.

Note that to be inconsistent with my previous plot I used a linear scale along the bottom this time.

Posted by: Simon Willerton on April 18, 2013 6:00 PM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

I’m afraid I don’t have any insight into any of your questions however I do have a comment on these graphs, the operation of edge contraction and their appearance in geometric group theory.

One may define a category of graphs with morphisms generated by (non-loop) edge contractions along with graph isomorphisms and this category has some very nice properties indeed: 1) Each morphism can be uniquely factored into either a subforest contraction and then an isomorphism, or alternatively an isomorphism and then forest contraction. 2) Since every morphism preserves the rank and connectivity of the graph, the category splits into components. The nerve of the component of connected rank r graphs is a classifying space for the outer automorphism group of the free group on r generators.

I’m sure this doesn’t help directly with your problem, but it does further motivate the study of graphs as objects in some category (if it needed more motivation). I suppose it also raises the possibility that the Tutte polynomials can be defined as a generating series counting the number of morphisms from minimal objects in a suitably defined category of graphs; this may agree with the spanning forest definition.

Posted by: James Griffin on April 17, 2013 12:03 PM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

A few notes:

First: It’s a little misleading to say that the Tutte polynomial doesn’t know the number of vertices. It does if you restrict yourself to connected graphs, and Tutte polynomials of disconnected graphs are determined from those of connected graphs. I usually like to think of Tutte as only existing in the connected case, although I know that isn’t standard.

Second: The Tutte specialization T(x,0)T(x,0) is also unaltered by multiple edges and behaves in a very simple way for loops: T(x,0)=0T(x,0)=0 if the graph has a loop. So you might want to look at that part of Tutte. T(x,0)T(x,0) is very closely related to the chromatic polynomial of GG; see here and here.

Third: Let GG and HH be two graphs with u 1u_1 and v 1v_1 vertices of GG, and u 2u_2 and v 2v_2 vertices of HH. Let XX be the graph obtained by gluing GG to HH with (u 1,u 2)(u_1, u_2) and (v 1,v 2)(v_1, v_2) identified; let YY be the graph obtained by gluing GG to HH with (u 1,v 2)(u_1, v_2) and (v 1,u 2)(v_1, u_2) identified.

The graphs XX and YY are said to differ by a “Whitney twist”. They have the same matroid and, in particular, the same Tutte polynomial. Do they have the same magnitude? I calculated one example and, to my surprise, the answer was yes!

This seems related to the (still unexplained, yes?) observation that m(X)=m(G)+m(H)m(GH)m(X) = m(G) + m(H) - m(G \cap H) for X=GHX = G \cup H in many cases.

Posted by: David Speyer on April 17, 2013 6:32 PM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

OK, I just checked the Whitney twist of two random 1010 vertex graphs GG and HH. They had the same magnitude.

I wonder whether this might be a true statement about Metric spaces. Let GG and HH be two metric spaces, with uu and vGv \in G and uu' and vHv' \in H obeying d(u,v)=d(u,v)=:dd(u,v) = d(u',v') =: d. Let MM be the two element metric space whose two elements have distance dd.

Let XX be the push out of GMHG \leftarrow M \rightarrow H. Let YY be the similar pushout, but where we twist the map MHM \rightarrow H so that uu gets glued to vv' and vv to uu'.

Do we get μ(X)=μ(Y)\mu(X) = \mu(Y)?

Posted by: David Speyer on April 17, 2013 9:10 PM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

Not a general fact about metric spaces. Take the 33 GG and HH to be the element metric spaces with distances (7,8,10)(7,8,10) and (7,5,10)(7,5,10). We can glue them to either (0 7 8 13 7 0 10 7 8 10 0 5 13 7 5 0 )\begin{pmatrix} 0 & 7 & 8 & 13 \\ 7 & 0 & 10 & 7 \\ 8 & 10 & 0 & 5 \\ 13 & 7 & 5 & 0 \\ \end{pmatrix}

and

(0 7 8 12 7 0 10 5 8 10 0 7 12 5 7 0 )\begin{pmatrix} 0 & 7 & 8 & 12 \\ 7 & 0 & 10 & 5 \\ 8 & 10 & 0 & 7 \\ 12 & 5 & 7 & 0 \\ \end{pmatrix}

(These are both pushouts in the category of metric spaces, if I am not confused.)

These do NOT have same magnitude.

Why the heck did it work for two moderately large random graphs? (Of course, coding error should be considered. I’d love it if someone else would check my work.)

Posted by: David Speyer on April 17, 2013 10:18 PM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

I checked through the whole of this example and agree with you. (For the record, it’s the two points distance 10 apart, not the two distance 7 apart, that we’re gluing along.) With a scale factor of 0.1, the magnitudes of the two spaces are respectively

1.71428374384555,1.70477104166411 1.71428374384555\ldots, \quad 1.70477104166411\ldots

according to my computations.

Posted by: Tom Leinster on April 18, 2013 1:06 AM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

All very interesting, David: thanks.

It’s a little misleading to say that the Tutte polynomial doesn’t know the number of vertices. It does if you restrict yourself to connected graphs.

Fair enough. Would you find it less misleading to say that the Tutte polynomial doesn’t know the number of connected-components?

I’ll add a note to the main post.

I hope I’m not mistaken in thinking that for a graph G=(V,E)G = (V, E), the degree of T G(x,y)T_G(x, y) as a polynomial in xx (with yy thought of as constant) is |V||π 0(G)|\left|V\right| - \left|\pi_0(G)\right|. So if you know the Tutte polynomial, the number of components determines the number of vertices and vice versa.

Second: The Tutte specialization T(x,0)T(x,0) is also unaltered by multiple edges and behaves in a very simple way for loops: T(x,0)=0T(x,0)=0 if the graph has a loop. So you might want to look at that part of Tutte. T(x,0)T(x,0) is very closely related to the chromatic polynomial of GG

Actually, where I began was a comparison of the magnitude function and the chromatic polynomial. I only later remembered that the chromatic polynomial is essentially a specialization of the Tutte polynomial. But of course I may well have missed something, and what you say does suggest focusing attention there.

…Whitney twist…

I’ll have to think about all this: it seems rather perplexing.

A friend suggested that “Whitney twist” would be a great name for a cocktail. But it’s something else too.

Posted by: Tom Leinster on April 17, 2013 11:46 PM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

“Fair enough. Would you find it less misleading to say that the Tutte polynomial doesn’t know the number of connected-components?”

Yes, that’s a good way to put it.

Some more data on Whitney twists. I generated another two random graphs on 1010 vertices, with edge inclusion probability 0.40.4. For the record, they are

G = {{3, 1}, {4, 1}, {5, 1}, {5, 3}, {5, 4}, {6, 1}, {6, 2}, {6, 3}, {7, 1}, {7, 4}, {7, 5}, {7, 6}, {8, 1}, {8, 2}, {8, 3}, {8, 5}, {8, 6}, {9, 1}, {9, 2}, {9, 3}, {9, 4}, {9, 5}, {10, 4}, {10, 6}, {10, 8}, {10, 9}}

and

H = {{3, 1}, {4, 2}, {5, 1}, {5, 2}, {5, 3}, {6, 2}, {6, 3}, {6, 4}, {6, 5}, {7, 2}, {7, 3}, {7, 4}, {7, 6}, {8, 1}, {8, 2}, {8, 3}, {8, 4}, {8, 5}, {8, 6}, {8, 7}, {9, 2}, {9, 3}, {9, 6}, {9, 7}, {9, 8}, {10, 1}, {10, 2}, {10, 6}, {10, 8}, {10, 9}}

Note that they are not isomorphic, since HH has a vertex of degree 99 and GG does not. Let XX be the result of gluing 11 and 22, in HH, to 99 and 1010 in GG. Let YY be the result of gluing 11 and 22 in HH to 1010 and 99 in GG. Again, XX and YY are not isomorphic, because XX has a vertex of degree 1111, and YY does not.

It turns out XX and YY have the same magnitude! Specifically, it is f/gf/g where f=-18 - 194 q - 472 q^2 + 1262 q^3 + 6040 q^4 - 60 q^5 - 24852 q^6 - 16116 q^7 + 47834 q^8 + 46626 q^9 - 45694 q^10 - 57030 q^11 + 19818 q^12 + 34190 q^13 - 2894 q^14 - 10134 q^15 + 500 q^16 + 1368 q^17 - 462 q^18 - 58 q^19 + 116 q^20 - 2 q^21 - 8 q^22 and g = -1 - 17 q - 97 q^2 - 137 q^3 + 646 q^4 + 2324 q^5 + 123 q^6 - 8921 q^7 - 8819 q^8 + 12941 q^9 + 23403 q^10 - 3597 q^11 - 24618 q^12 - 7678 q^13 + 10408 q^14 + 5998 q^15 - 1063 q^16 - 925 q^17 - 22 q^18 - 118 q^19 - 92 q^20 + 2 q^21 + 16 q^22 + 4 q^23.

The denominator does not factor, and I cannot find any relation between this rational function and the magnitudes of GG and HH.

But that isn’t the strangest thing! I computed the vectors P X(q) 1(1,1,,1) TandP Y(q) 1(1,1,,1) TP_X(q)^{-1} (1,1,\ldots,1)^T \quad \mathrm{and} \quad P_Y(q)^{-1} (1,1,\ldots,1)^T

They were exactly the same!

What’s going on here?

Posted by: David Speyer on April 18, 2013 2:29 PM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

That’s strange and very interesting, especially that

I cannot find any relation between this rational function and the magnitudes of GG and HH.

Can you tell me the vectors

Z X(q) 1(1,,1) TandZ Y(q) 1(1,,1) T? Z_X(q)^{-1}(1, \ldots, 1)^T \quad \text{and} \quad Z_Y(q)^{-1}(1, \ldots, 1)^T?

These are what we call the “weightings” on XX and YY.

To answer your earlier question, you’re right that there are many situations in which the equation |AB|=|A|+|B||AB|\left|A \cup B\right| = \left|A\right| + \left|B\right| - \left|A \cap B\right| appears to hold, but no one knows how to prove it. (Example: AA, BB and ABA \cup B are compact convex subsets of Euclidean space.)

There are some very restricted situations in which it is known, such as the one mentioned in Proposition 2.3.2 here. However, the hypotheses used there don’t hold in the Whitney twist situation. And in fact it’s clear that they don’t, because if they did then there’d be an easy inclusion-exclusion-type formula for μ X\mu_X and μ Y\mu_Y in terms of μ G\mu_G and μ H\mu_H.

Posted by: Tom Leinster on April 18, 2013 4:32 PM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

First of all, typo above. I was computing the weightings, which are Z 1(1,1,,1) TZ^{-1} (1,1,\ldots,1)^T, not P 1(1,1,,1) TP^{-1} (1,1, \ldots, 1)^T.

They are precisely the same. All the terms have the same denominator, which is the polynomial gg above. The vector of numerators is pretty long to post onto a comment thread, so I’ll upload it here.

Posted by: David Speyer on April 18, 2013 5:16 PM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

Thanks! No time to think now, but there’s obviously something going on here.

Posted by: Tom Leinster on April 18, 2013 5:22 PM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

I realize that I don’t understand exactly what you mean when you say that the weightings on XX and YY are “the same”.

The graph XX is formed from GG and HH by gluing vertex 9 of GG to vertex 1 of HH (making a new vertex {9,1}\{9, 1\}) and gluing vertex 10 of GG to vertex 2 of HH (making a new vertex {10,2}\{10, 2\}). So the 18 vertices of XX are the vertices 1,,81, \ldots, 8 of GG, the vertices 3,,103, \ldots, 10 of HH, and these two new vertices, {9,1}\{9, 1\} and {10,2}\{10, 2\}.

The graph YY is formed from GG and HH by gluing vertex 9 of GG to vertex 2 of HH (making a new vertex {9,2}\{9, 2\}) and gluing vertex 10 of GG to vertex 1 of HH (making a new vertex {10,1}\{10, 1\}). So the 18 vertices of YY are the vertices 1,,81, \ldots, 8 of GG, the vertices 3,,103, \ldots, 10 of HH, and these two new vertices, {9,2}\{9, 2\} and {10,1}\{10, 1\}.

When you say that the weighting w Xw_X on XX is the same as the weighting w Yw_Y of YY, presumably that means for a start that w Xw_X and w Yw_Y agree on the vertices 1,,81, \ldots, 8 of GG and the vertices 3,,103, \ldots, 10 of HH. But are you saying that

w X({9,1})=w Y({9,2})andw X({10,2})=w Y({10,1}) w_X(\{9, 1\}) = w_Y(\{9, 2\}) \quad \text{and} \quad w_X(\{10, 2\}) = w_Y(\{10, 1\})

or that

w X({9,1})=w Y({10,1})andw Y({10,2})=w Y({9,2})? w_X(\{9, 1\}) = w_Y(\{10, 1\}) \quad \text{and} \quad w_Y(\{10, 2\}) = w_Y(\{9, 2\})?

They can’t both be true, as if they were then we’d have w X({9,1})=w X({10,2})w_X(\{9, 1\}) = w_X(\{10, 2\}), whereas your table shows that no two weights are equal. And choosing one over the other seems arbitrary.

Posted by: Tom Leinster on April 18, 2013 10:03 PM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

David, here’s something else that puzzles me. If I try reproducing your experiment but with two known, small graphs, I get different behaviour.

Let GG and HH both be this graph:   o—o—o. Choose two adjacent vertices uu and vv of GG, and two adjacent vertices uu' and vv' of HH. Glue GG and HH together in the usual two ways: either glue uu to uu' and vv to vv', or glue uu to vv' and vv to uu'. One of the results, XX, is a 4-vertex graph shaped like a T. The other, YY, is   o—o—o—o.

Then XX and YY have the same magnitude functions (being trees with the same number of edges) but different weightings. Am I understanding what you did and imitating it correctly? If so, we have the peculiar situation that an equation holds for a couple of randomly-chosen 10-vertex graphs, but fails in a small simple example!

Posted by: Tom Leinster on April 19, 2013 12:51 AM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

I agree – you are imitating me correctly, and the surprising behavior which happened in the large random example does not happen in this small case.

And yet, as you say, the magnitude still works out.

Curiouser and curiouser…

Posted by: David Speyer on April 19, 2013 1:32 AM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

Tom asked David:

When you say that the weighting w Xw_X on XX is the same as the weighting w Yw_Y of YY, presumably that means for a start that w Xw_X and w Yw_Y agree on the vertices 1,,81,\dots,8 of GG and the vertices 3,,103,\dots,10 of HH.

I’ve done the calculations in maple and get that, yes.

Tom then asked David:

But are you saying that w X({9,1})=w Y({9,2})andw X({10,2})=w Y({10,1}) w_X(\{9, 1\}) = w_Y(\{9, 2\}) \quad \text{and} \quad w_X(\{10, 2\}) = w_Y(\{10, 1\}) or that w X({9,1})=w Y({10,1})andw Y({10,2})=w Y({9,2})? w_X(\{9, 1\}) = w_Y(\{10, 1\}) \quad \text{and} \quad w_Y(\{10, 2\}) = w_Y(\{9, 2\})?

I don’t know what David was claiming but I get, for some denominator DD, w X({9,1}) =(4q 224q 21+46q 20+7q1)/D w X({10,2}) =(4q 2214q 21+48q 20+6q1)/D w Y({9,2}) =(4q 2212q 21+54q 20+4q1)/D w Y({10,1}) =(4q 226q 21+40q 20+9q1)/D\begin{aligned} w_X(\{9, 1\}) &= (-4q^22-4q^21+46q^20+\dots-7q-1)/D\\ w_X(\{10, 2\})&=(-4q^22-14q^21+48q^20+\dots-6q-1)/D\\ w_Y(\{9, 2\})&=(-4q^22-12q^21+54q^20+\dots-4q-1)/D\\ w_Y(\{10, 1\})&=(-4q^22-6q^21+40q^20+\dots-9q-1)/D \end{aligned}

So there are no equalities there, but w X({9,1})+w X({10,2}=w Y({9,2})+w Y({10,1})w_X(\{9, 1\})+w_X(\{10, 2\}= w_Y(\{9, 2\})+w_Y(\{10, 1\}) which gives that XX and YY have the same magnitude.

I have, unscientifically, run this with some more random graphs with ten vertices for GG and HH and seem to get this behaviour half the time. Don’t have time to look into this anymore at the moment.

Posted by: Simon Willerton on April 19, 2013 11:55 AM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

Simon wrote:

I have, unscientifically, run this with some more random graphs with ten vertices for G and H and seem to get this behaviour half the time.

What do you mean by “this behaviour”? In particular, do you have evidence to contradict the conjecture that graphs differing by a Whitney twist have the same magnitude function?

Posted by: Tom Leinster on April 20, 2013 2:09 AM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

Here’s a possible counter-example and a new conjecture!

Take the complete graph on five vertices and remove the edges (1,2)(1,2) and (2,3)(2,3). Call this GG then take the Whitney twist pair of GG with itself using vertices 11 and 22 on both copies of GG. These two graphs have different magnitudes.

Note that there is not an edge between the identified vertices in any of the graphs.

If we take two (connected) graphs GG and HH each with a distinguished edge, say e Ge_G and e He_H, then we can form the Whitney twist pair using the end-points of e Ge_G and e He_H (removing the extra edge after gluing). David’s example is basically of this form. The hundreds of examples of this form that I’ve done all result in the Whitney twisted pair having the same magnitude.

One could then conjecture that a Whitney twist pair of graphs that have an edge between the pivoting vertices have the same magnitude.

Posted by: Simon Willerton on April 20, 2013 2:59 PM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

Interesting!

First of all, this means the Tutte polynomial doesn’t determine the magnitude. Tutte polynomial is always invariant under Whitney twist.

So, it seems like magnitude is unaltered by twisting along two vertices which are close to each other.

You showed above that, if we glue a single vertex of GG to a single vertex of HH to form XX, then μ X=μ G+μ H1\mu_X = \mu_G + \mu_H - 1. Maybe there is a similar recursion that holds if we glue along a “small” subgraph?

Posted by: David Speyer on April 21, 2013 3:11 PM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

That’s progress! Thanks, David and Simon, for answering this question.

I find Simon’s conjecture quite plausible, because it’s a pushout along a pair of isometries. David’s example back here wasn’t, and I’m at a loss to explain why his two Whitney-differing graphs have the same magnitude.

Here’s a stronger version of Simon’s conjecture. Take graphs KK, GG and HH, and isometries

GKH. G \longleftarrow K \longrightarrow H.

Suppose that the image of KK in GG has the following convexity property: if x,y,zGx, y, z \in G with d(x,y)+d(y,z)=d(x,z)d(x, y) + d(y, z) = d(x, z), and xx and zz both belong to the image of KK, then so does yy. Suppose the same is true of the image of KK in HH.

Conjecture: |G+ KH|=|G||K|+|H|\left|G +_K H\right| = \left|G\right| - \left| K \right| + \left| H\right|.

Here G+ KHG +_K H is the pushout.

But maybe Simon can immediately defeat this conjecture. Simon, you say you’ve tried hundreds of examples where KK is the graph consisting of a single edge. Is it the case in all of them that the magnitude of the glued graph is |G|21+q+|H|\left|G\right| - \frac{2}{1 + q} + \left| H\right|? If not, the conjecture’s false.

Posted by: Tom Leinster on April 22, 2013 1:09 AM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

This whole conversation has prompted a realization that I’m quite excited by:

Graphs are like convex sets.

Here’s what I mean. Let’s view graphs as metric spaces. The metric space arising from a graph has a couple of special properties.

First, all distances are integers. (If you like, it’s a category enriched in ({},,0,+)(\mathbb{N} \cup \{\infty\}, \geq, 0, +), just as a metric space is a category enriched in ([0,],,0,+)([0, \infty], \geq, 0, +).) This is why the magnitude function of a graph is a rational functionn.

Second, the metric is in a suitable sense geodesic. A metric space XX is geodesic if for all x,yXx, y \in X there exists an isometry γ:[0,d(x,y)]X\gamma\colon [0, d(x, y)] \to X such that γ(0)=x\gamma(0) = x and γ(d(x,y))=y\gamma(d(x, y)) = y. Of course, that isn’t literally true for the metric space coming from a graph, but if you adapt the definition of geodesic to the discrete situation, something very similar is true. For nn \in \mathbb{N}, write [n][n] for the graph

0 — 1 — 2 — \cdotsnn.

Then the metric space XX coming from a graph has the following geodesic-like property: for all x,yXx, y \in X there exists an isometry γ:[d(x,y)]X\gamma\colon [d(x, y)] \to X such that γ(0)=x\gamma(0) = x and γ(d(x,y))=y\gamma(d(x, y)) = y.

So the conjecture I just made is something like the conjecture that for compact convex subsets G,HG, H of n\mathbb{R}^n,

|GH|=|G||GH|+|H|. \left| G \cup H \right| = \left|G\right| - \left|G \cap H\right| + \left|H\right|.

This latter conjecture seems to be pretty hard. Part of the difficulty is that the spaces involved are not finite, so there are analytical issues. But maybe the case of graphs is easier. In that case, it might point the way to the solution of the conjecture on convex sets.

Posted by: Tom Leinster on April 22, 2013 1:24 AM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

Of course the inclusion-exclusion formula does at least hold for trees, which you can nicely characterize as those graphs for which each xx and yy are connected by a unique “geodesic” of the type you describe.

Posted by: Mark Meckes on April 22, 2013 11:50 AM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

Well, almost. You actually have to weaken the definition of “geodesic” a little further to characterize trees that way, to resemble the differential geometers’ notion of a locally length-minimizing path. Otherwise a cycle with an odd number of vertices also has a unique geodesic between each pair of vertices.

Posted by: Mark Meckes on April 22, 2013 12:10 PM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

You’ll be unsurprised to hear that I’d already considered inclusion-exclusion. However, it’s easy to find a counter-example. Let the interval II be the connected graph with two vertices, the triangle TT be the complete graph on three vertices and let the braced diamond DD be the four vertex graph obtained by glueing two triangles along a subgraph II.

Then |I| =21+q=22q+2q 22q 3+2q 4+O(q 5) |T| =31+2q=36q+12q 224q 3+48q 4+O(q 5) |D| =2(q2)2q+q 21=410q+24q 258q 3+140q 4+O(q 5)\begin{aligned} |I|&= \frac{2}{1+q}=2-2q+2 q^2-2 q^3+2 q^4+O(q^5) \\ |T|&=\frac{3}{1+2q}=3-6q+12q^2-24q^3+48q^4+O(q^5) \\ |D|&=\frac{2(q-2)}{-2q+q^2-1} =4-10q+24q^2-58q^3+140q^4+O(q^5)\end{aligned} so |D|2|T|+|I|=2q 212q 3+46q 4+O(q 5)0.|D|-2|T|+|I|=2q^2-12q^3+46q^4+O(q^5)\neq 0.

Note that the inclusion-exclusion formula will work mod q 2q^2 as the constant and linear terms are just, up to a factor, the number of vertices and number of edges.

Another guess/conjecture one might make is that the magnitude of the union along an edge is independent of which edge is chosen. This also seems to be false. You can glue a triangle TT onto a braced diamond DD along an edge in two different ways. These give rise to different graphs with different magnitudes, namely 514q+36q 294q 3+246q 4+O(q 5)5 - 14 q + 36 q^2 - 94 q^3 + 246 q^4 + O(q^5) and 514q+38q 2104q 3+284q 4+O(q 5).5 - 14 q + 38 q^2 - 104 q^3 + 284 q^4 + O(q^5).

Posted by: Simon Willerton on April 22, 2013 9:40 AM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

Hmph. Thanks.

Nevertheless, we’ve now amassed quite a few unexplained identities for magnitudes of glued graphs:

In both these cases, the magnitude is the same for the two graphs that differ by a Whitney twist. But that magnitude is not in general given by an inclusion-exclusion formula.

However, there are also situations where the magnitude of a glued graph is given by an inclusion-exclusion formula:

  • My Proposition 2.3.2 says that this happens for gluings of metric spaces under very restrictive hypotheses. For graphs, this does cover the case where we’re gluing at a single point, as well as disjoint unions, but it hardly covers anything else in the present discussion.

  • Mark notes that the inclusion-exclusion formula holds when we glue two trees together along a subtree.

  • There are odd other examples. For instance, glue a 4-cycle to a 3-cycle along a single edge. Then the magnitude of the result is what the inclusion-exclusion formula suggests. It’s interesting that this works, but it doesn’t work if you replace the 4-cycle by a 3-cycle: that was Simon’s counterexample.

I’d love to know a general result that encompasses all these scattered cases.

Posted by: Tom Leinster on April 22, 2013 3:24 PM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

Tom wrote:

My Proposition 2.3.2 … does cover the case where we’re gluing at a single point, as well as disjoint unions, but it hardly covers anything else in the present discussion.

To be fair, it also covers gluing two trees along a subtree (although I didn’t notice that until after seeing Simon’s explicit formula for the magnitude of trees). For what it’s worth, together with a limiting procedure it even covers gluing of metric trees along subtrees.

Posted by: Mark Meckes on April 22, 2013 6:22 PM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

The paper you link to begins with the words:

The study of injective envelopes of metric spaces, also known as metric trees, (T-theory or \mathbb{R}-trees) began with J. Tits [52] in 1977

… so either they mean something different from what I’m used to by “injective envelope”, or they’re unaware of Isbell’s foundational 1964 paper on injective envelopes of metric spaces.

Posted by: Tom Leinster on April 23, 2013 12:27 PM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

Good point… I actually realized I’d goofed up while I was on the train with no internet access, but you beat me to it.

Posted by: Tom Leinster on April 22, 2013 10:22 PM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

On the same note, there’s something else my Proposition 2.3.2 does, which I hadn’t given it credit for.

First let me rephrase Proposition 2.3.2 a little bit, to suit our present purposes (and to save anyone else the bother of reading it).

Suppose we have a graph GG and a subgraph KK whose induced metric is the same as the subspace metric from GG. (Again, this is a kind of convexity condition on KK.) Say that GG projects to KK if for all gGg \in G there exists π(g)K\pi(g) \in K such that for all kKk \in K,

d(g,k)=d(g,π(g))+d(π(g),k). d(g, k) = d(g, \pi(g)) + d(\pi(g), k).

Assuming that GG is connected (i.e. distances are finite), π(g)\pi(g) must be the unique closest point of KK to gg. This justifies the functional notation.

The result is this. Let GG be a graph containing a subgraph KK satisfying the conditions above, and let HH be another graph also containing a copy of KK, subject to the same conditions. Let G+ KHG +_K H be the pushout, i.e. the graph obtained by gluing GG to HH along KK. Then G+ KHG +_K H has a weighting obtained from the weightings of GG, HH and KK in the obvious inclusion-exclusion way, and

μ G+ KH=μ G+μ Hμ K. \mu_{G +_K H} = \mu_G + \mu_H - \mu_K.

Special case: KK is the graph consisting of a single edge. Then we can forget about one of the conditions above: it’s automatic that the induced metric on KK is the same as the subspace metric inherited from any graph GG it’s embedded in. When does GG project to KK? Exactly when GG contains no vertices equidistant from the two vertices of KK. So if I’m not mistaken, we have:

Theorem Take a graph GG with distinguished vertices uu and vv, joined by an edge, such that no vertex of GG equidistant from uu and vv. Take HH, uu' and vv' subject to the same conditions. Let JJ be the graph formed from the disjoint union of GG and HH by identifying the edge uvu v with the edge uvu' v' (either way round). Then

μ J(q)=μ G(q)+μ H(q)21+q. \mu_J(q) = \mu_G(q) + \mu_H(q) - \frac{2}{1 + q}.

For example, if you glue two even cycles along an edge, the resulting graph has magnitude given by the inclusion-exclusion formula.

This doesn’t explain why the same is true when you glue a 4-cycle to a 3-cycle, though.

Posted by: Tom Leinster on April 23, 2013 12:01 AM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

Nice! This ties in nicely with the fact that the quadratic “correction term” N 1(a,b)N 1(c,d)N_1(a,b)N_1(c,d) involves counting numbers of points equidistant from the vertices of the distinguished edges.

Given that this correction vanishes if either GG or HH satisfies the no-equidistant-points condition, have you looked at the ‘edge sum’ (*) of an arbitrary even cycle with an arbitrary odd cycle?

(*) We should try to fix some terminology!

Posted by: Simon Willerton on April 23, 2013 9:07 AM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

If I’m not mistaken, I can do better than that. I believe I can prove:

Theorem  Let XZY X \longleftarrow Z \longrightarrow Y be distance-preserving maps of finite metric spaces. Suppose that XX projects to the image of ZZ. (We don’t suppose that YY projects to the image of ZZ.) If XX and YY have magnitude then so do ZZ and the pushout X+ ZYX +_Z Y, and |X+ ZY|=|X|+|Y||Z|. \left| X +_\Z Y\right| = \left|X\right| + \left|Y\right| -\left|Z\right|.

The weighting on the pushout is defined in the obvious inclusion-exclusion way.

(This is reminiscent of the following fact: for a pushout of finite sets XZYX \leftarrow Z \rightarrow Y to have cardinality given by the inclusion-exclusion formula, it suffices that just one of the two given maps is injective.)

If we’re interested in gluing two graphs along an edge, this theorem tells us that only one of the two need satisfy the no-equidistant-points property in order for inclusion-exclusion to hold. So if you start with a graph GG, you can merrily edge-glue lots of even cycles onto it, or indeed any other bipartite graphs, and the result has magnitude given by the inclusion-exclusion formula.

This theorem covers everything in my second list of identities. It also tells us that the edge-sum of an arbitrary even cycle with an arbitrary odd cycle has magnitude given by inclusion-exclusion.

Posted by: Tom Leinster on April 23, 2013 11:20 AM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

Excellent. That’s the result I would have hoped that you could prove.

It actually reminds me of Base Change or Beck-Chevalley condition. Very vaguely, and possibly incorrectly, in that situation you have a pullback square X× ZY p Y q f X g Z \begin{matrix} X\times_Z Y& \xrightarrow{p} & Y \\ q\downarrow&&\, \downarrow f\\ X &\underset{g}{\to} & Z \end{matrix} and you want push-pull equals pull-push, e.g. f g =p q {f^\star } {g_\star} = p_\star q^\star , whatever these things mean. It seems that this will hold under asymmetric hypotheses on the pair of morphisms XgZfYX\xrightarrow{g} Z \xleftarrow{f} Y such as either ff or gg being a fibration. Don’t ask me to be precise here. It’s an old desire of mine to understand this in the right context. (The right context for me, that is.)

Posted by: Simon Willerton on April 23, 2013 1:49 PM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

David S’s example falls into my class of examples (or rather, my class of examples generalizes his example). He has edge {10,9}\{10,9\} in GG and so in XX and YY there’s an edge joining the vertices that are twisted over.

Posted by: Simon Willerton on April 22, 2013 4:22 PM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

Oh I see. Thanks. The point is that although there isn’t an edge in HH joining the two vertices in question, there might as well be, because we’re not saying anything about how the magnitudes of the two glued graphs depend on the magnitudes of GG and HH — just that the magnitudes of the two glued graphs are equal.

Posted by: Tom Leinster on April 22, 2013 4:32 PM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

I haven’t time to think about this now, but it might be easy to think about the quadratic term in the magnitude for the pushout. Given two connected graphs GG and HH with a specified edge in each of them then there are two pushouts XX and YY we can form, depending on how we identify the edges. We know that the constant and linear terms in the magnitude of XX and YY are equal are they just depend on the number of vertices and edges. We have formulas above for the quadratic term in the magnitude. Can you show that XX and YY have the same quadratic term in the magnitude?

Posted by: Simon Willerton on April 22, 2013 11:45 AM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

Okay. I can tell you what the quadratic term is when you glue along an edge. Suppose {a,b}\{a,b\} is an edge in GG and {c,d}\{c,d\} is an edge in HH. Let TT denote the coefficient of q 2q^2 in the magnitude as above (this conflicts with TT denoting the complete graph in this other comment above, but both stand for ‘triangle’).

If the inclusion-exclusion principle were to hold then the quadratic coefficient T(G+ IH)T(G +_I H) of GG glued to HH along the specified edges, would be given by T(G)+T(H)T(I)T(G)+T(H)-T(I), i.e. by T(G)+T(H)2T(G)+T(H)-2. However, it is actually given by T(G)+T(H)2+2N 1(a,b)N 1(c,d)T(G)+T(H)-2+2N_1(a,b)N_1(c,d) where N 1(a,b)N_1(a,b) is the number of vertices in GG which are distance one from both aa and bb, this can be thought of as the number of triangles in GG with base {a,b}\{a,b\}, and similarly for N 1(c,d)N_1(c,d).

Note that this does not depend on whether aa is glued to cc and bb is glued to dd or the other way round, so the quadratic term in the magnitude is independent of the way the gluing is done and the conjecture holds to the quadratic term at least.

Note also that the quadratic coefficients of 3636 and 3838 in the magnitude of the two different ways of glueing the triangle to the braced diamond above are correctly given by this formula. (That’s a sanity check for me.)

Posted by: Simon Willerton on April 22, 2013 5:57 PM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

Let AA be the adjacency matrix of our graph. Let P G(q)= d=0 q dA dP_G(q) = \sum_{d=0}^{\infty} q^d A^d. So P G(q)=(1qA) 1P_G(q) = (1-q A)^{-1}, we see that P G(q) 1=1qAP_G(q)^{-1} = 1 - q A and the sum of the entries of P G(q) 1P_G(q)^{-1} is |vertices|2|edges|q|\mathrm{vertices}| - 2 |\mathrm{edges}| q.

Each entry of P G(q)P_G(q) is a power series in qq. The leading term of P G(q) ijP_G(q)_{ij} is cq d(i,j)c q^{d(i,j)} for some positive constant cc. So Z G(q)Z_G(q) is something like a “low degree truncation” of P G(q)P_G(q). This explains why the first two terms of the magnitude are |vertices|2|edges|q|\mathrm{vertices}| - 2 |\mathrm{edges}| q.

If we could make a more precise statement about the relation between Z GZ_G and P GP_G, we could probably make a more precise relation between the magnitude of GG and |vertices|2|edges|q|\mathrm{vertices}| - 2 |\mathrm{edges}| q.

Posted by: David Speyer on April 17, 2013 6:53 PM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

OK, so for vertices ii and jj,

P G(q) ij= d=0 (number of length  d  paths from  i  to  j)q d. P_G(q)_{i j} = \sum_{d = 0}^\infty (\text{number of length }  d  \text{ paths from }  i   \text{ to }  j)\cdot q^d.

I’m pretty confused now. Given a graph GG, there are three different matrices whose magnitude we might wish to consider:

  • P G(q)P_G(q)

  • Z G(q)Z_G(q) (whose magnitude is the magnitude of the metric space GG)

  • the adjacency matrix A GA_G, or perhaps qA Gq A_G. (I thought a bit about the magnitude and maximum diversity of adjacency matrices in Example 4.2 here. It has something to do with clique numbers.)

What I’m not seeing right now is how these three magnitudes are related.

Posted by: Tom Leinster on April 18, 2013 12:15 AM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

Here, maybe, is another piece of this puzzle.

As you noted, (A d) ij(A^d)_{i j} is the number of paths of length dd from ii to jj. Similarly, ((I+A) d) ij((I+A)^d)_{i j} is the number of paths of length d\le d from ii to jj. So let’s define, for a matrix MM, a matrix Γ(M)\Gamma(M) whose i,ji,j entry is 11 if m ij0m_{i j} \neq 0, and 00 otherwise. (This has a standard name which I’ve forgotten, and Γ\Gamma may or may not be a standard notation for it.) Then Γ((I+A) d)\Gamma((I+A)^d) tells you exactly which vertices have distance d\le d from each other. Therefore Z G(q)= d=0 Γ((I+A) d)q d d=0 Γ((I+A) d)q d+1=(1q) d=0 Γ((I+A) d)q d. Z_G(q) = \sum_{d=0}^\infty \Gamma((I+A)^d) q^d - \sum_{d=0}^\infty \Gamma((I + A)^d) q^{d+1} = (1-q) \sum_{d=0}^\infty \Gamma((I+A)^d) q^d.

So now let’s define yet another matrix, Q G(q)=(1q) d=0 (I+A) dq d=I+ d=1 (I+A) d1Aq d, Q_G(q) = (1-q) \sum_{d=0}^\infty (I+A)^d q^d = I + \sum_{d=1}^\infty(I + A)^{d-1} A q^d, so that Z G(q)Z_G(q) is a somewhat different sort of “truncation” of Q G(q)Q_G(q). To first order in qq, Q G(q)Q_G(q) and P G(q)P_G(q) are both I+qAI + q A.

It may be worth noting that your example relating to clique numbers was to do with reflexive graphs, so maybe I+qAI + q A (for a simple graph) is what’s really involved there, too.

Posted by: Mark Meckes on June 12, 2014 9:36 AM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

Actually, (I+A) d(I+A)^d isn’t exactly what I said (paths of different lengths get weighted differently), but Γ((I+A) d)\Gamma((I+A)^d) is what I said, so the rest is correct (I think).

Posted by: Mark Meckes on June 12, 2014 4:02 PM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

I’m about to get on a train, where I plan to think about David’s intriguing observations.

A quick pair of questions first. Given polynomials ff and gg over \mathbb{Q}, we can talk about the degree of the rational function f/gf/g in at least two senses:

  • The “asymptotic degree”, deg(f)deg(g)deg(f) - deg(g). When qq is large, f(q)/g(q)f(q)/g(q) behaves roughly like q dq^d, where dd is the asymptotic degree.

  • The topological degree, max{deg(f),deg(g)}max\{deg(f), deg(g)\} (where ff and gg have had any common factors removed). This is the degree of f/gf/g as an endomorphism of the Riemann sphere {}\mathbb{C} \cup \{\infty\}.

Question: What are the asymptotic and topological degrees of μ G\mu_G, for a graph GG?

I’ve only given this a few minutes’ thought, but didn’t immediately see an answer.

Posted by: Tom Leinster on April 18, 2013 7:19 PM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

An easy observation: if GG is homogeneous (meaning that its automorphism group acts transitively on vertices) then the topological degree is the diameter of GG, and the asymptotic degree is the negative of diameter.

This isn’t always true for non-homogeneous graphs: e.g. the bull and tadpole (above) have the same magnitude function but different diameters.

In all the examples I know of, the asymptotic degree is negative. I don’t know whether that’s always true.

Posted by: Tom Leinster on April 22, 2013 1:12 AM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

I’m very interested by the perspective of this post of going straight to the magnitude function by working over the rig of rational functions. For general finite metric spaces, in which distances need not be integers, you wouldn’t get rational functions, but we know that the magnitude function is still defined at all but finitely many points. I wonder if it would be enlightening to think of magnitude in general as built in terms of the rig kk of functions (0,)(0,\infty) \to \mathbb{R} defined on a cofinite set and modulo equality on cofinite sets, and the monoid homomorphism ||:([0,],+)(k,)\vert\cdot\vert :([0,\infty], +) \to (k,\cdot) given by |x|=(te tx)\vert x\vert = (t \mapsto e^{-tx}).

Posted by: Mark Meckes on May 3, 2013 3:44 PM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

I see what you mean. That way, you have the advantage that magnitude (or rather, the magnitude function) is always defined.

What we’d have to do for (positive definite) compact spaces isn’t clear to me, though.

Posted by: Tom Leinster on May 6, 2013 1:17 PM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

Right, for positive definite compact spaces it seems we’d have to do something more convoluted to fit into this perspective. It’s also less clear that it would be helpful in that setting, since magnitude is already always defined for such spaces (although — as far as we know so far — it may be infinite).

Posted by: Mark Meckes on May 6, 2013 2:47 PM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

Mark wrote:

I wonder if it would be enlightening to think of magnitude in general as built in terms of the rig kk of functions (0,)(0, \infty) \to \mathbb{R} defined on a cofinite set and modulo equality on cofinite sets, and the monoid homomorphism ||:([0,],+)(k,)|\cdot|: ([0, \infty], +) \to (k, \cdot) given by |x|=(te tx)|x| = (t \mapsto e^{-t x}).

I liked this idea, but something bothered me slightly about it. Thinking about it again, I think it’s that the rig seems unnecessarily big. In the graph case, we stick to rational polynomials (in e te^{-t}, effectively), rather than considering all (partial) functions \mathbb{Q} \to \mathbb{Q} defined on a cofinite set.

In the general case of metric spaces, I guess the analogue is as follows. First take the ring of functions (0,)(0, \infty) \to \mathbb{R} consisting of finite \mathbb{R}-linear combinations of functions of the form e txe^{-t x} (t0t \geq 0). This is an integral domain (e.g. because those basic functions are linearly independent), so it has a field of fractions KK. It’s a subrig of Mark’s kk, and is analogous to the (q)\mathbb{Q}(q) of the graph case. I don’t know whether KK or its elements have a standard name.

Posted by: Tom Leinster on August 16, 2013 12:45 PM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

Yes, that is more reasonable. I just wrote down the first easily described rig that occurred to me which would definitely be big enough. But it would certainly be more likely to clarify things to work explicitly in a more minimal setting.

Posted by: Mark Meckes on August 23, 2013 4:13 PM | Permalink | Reply to this
Read the post Whitney Twists
Weblog: The n-Category Café
Excerpt: Q. Is the magnitude of a graph invariant under Whitney twists? A. Sometimes.
Tracked: July 7, 2013 7:35 AM

Re: Tutte Polynomials and Magnitude Functions

Tom, here’s a small point, rather late in the day. You said

Having read the previous examples, you might have wondered whether the coefficients of the magnitude function (when expanded as a power series) always alternate in sign. The Petersen graph shows that they don’t.

The diligent reader might well not have wondered this, as on expanding out the formula given in Property/Example 7 for C 5C_5, the 55-cycle, they would have found

μ C 5(q)=510q+10q 2+0q 320q 4+40q 5+,\mu_{C_5}(q)= 5-10q +10q^2 + 0 q^3 -20 q^4 +40 q^5+\dots,

and this doesn’t have coefficients which alternate in sign.

As something of a teaser for a forthcoming paper by me and Richard Hepworth, I would say that the fact that the other graphs mentioned all have alternating sign coefficients can be explained by them having “diagonal magnitude homology”. I will, of course, report more details when we sort out the paper a little more.

Posted by: Simon Willerton on February 16, 2015 2:24 PM | Permalink | Reply to this

Re: Tutte Polynomials and Magnitude Functions

Good point! Though the Petersen graph arguably exhibits the non-alternation one coefficient earlier than C 5C_5 (depending on your attitude to the sign of 00).

Looking forward to your paper with Richard coming out.

Posted by: Tom Leinster on February 16, 2015 4:24 PM | Permalink | Reply to this

Post a New Comment