Tutte Polynomials and Magnitude Functions

April 16, 2013

Tutte Polynomials and Magnitude Functions

Posted by Tom Leinster

$MathML-enabled post (click for more details).$

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 $G$ into a polynomial $T_G$ in two variables, with natural number coefficients: $T_G(x, y) \in \mathbb{N}[x, y].$ The magnitude function of a graph is new and ill-understood. It turns a graph $G$ into a rational function $\mu_G$ in one variable, with rational coefficients: $\mu_G(q) \in \mathbb{Q}(q).$ It can also be expanded as a power series with integer coefficients: $\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.

$MathML-enabled post (click for more details).$

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 $V$ , a finite set $E$ , and a map $E \to (V \times V)/S_2$ . Here $(V \times V)/S_2$ is the quotient of $V \times V$ by the obvious action of the group $S_2$ of order $2$ ; it can be seen as the set of subsets of $V$ of cardinality 1 or 2. A graph without loops or multiple edges consists of a finite set $V$ and a subset $E \subseteq V \times V$ that, seen as a relation on $V$ , 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 $e$ of a graph $G$ , there are two fundamental operations we can perform:

Deletion. The graph $G - e$ is simply $G$ with the edge $e$ removed (but the vertices left untouched).
Contraction. The graph $G/e$ is formed from $G$ by first removing $e$ , then identifying the two vertices that it used to join.

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

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

$T_G = T_{G - e} + T_{G/e}$ if $e$ is neither a bridge nor a loop;
$T_G(x, y) = x^b y^\ell$ if $G$ consists of $b$ 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 $e$ 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 $G$ is the five-vertex graph at the top of the tree then $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 $A$ has a magnitude function $t \mapsto \left|t A\right|$ , where $t A$ is $A$ scaled up by a factor of $t$ and the bars indicate magnitude. (This “function” may have a finite number of singularities.) We can turn a graph $G$ 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^{-t}$ and write $\mu_G(q) = \left|t G\right|$ .

Now here’s a direct explanation.

List the vertices in some order: $v_1, \ldots, v_n$ . (The choice of order won’t affect anything.) Let $d_{i j}$ be the number of edges in a shortest path from $v_i$ to $v_j$ (assuming there is one). Let $Z_G(q)$ be the square matrix over $\mathbb{Q} [q]$ whose $(i, j)$ -entry is $q^{d_{i j}}$ , or $0$ if there is no path from $v_i$ to $v_j$ .

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

$\mu_G(q) \in \mathbb{Q}(q)$

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

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 $\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 $\det Z_G(q)$ is $1$ , which is invertible in $\mathbb{Z}$ . It follows that $1/\det Z_G(q)$ can be expanded as a power series over $\mathbb{Z}$ . Hence $\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_4$ :

4-cycle

We have

$\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 $G$ to be a forest with vertex-set $V$ and edge-set $E$ . Then

$\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 $\pi_0(G)$ is the set of connected-components of $G$ . 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 $\mu_G$ is determined by $\mu_{G-e}$ and $\mu_{G/e}$ whenever $e$ is an edge of $G$ 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.

Disjoint unions Any two graphs $G$ and $H$ have a disjoint union $G + H$ .

Tutte: $T_{G + H} = T_G T_H$ .

Magnitude: $\mu_{G + H} = \mu_G + \mu_H$ .
Joins Suppose we have a graph $G$ with a distinguished vertex $x$ , and another graph $H$ with a distinguished vertex $y$ . We can form a new graph $G * H$ , the “join”, by first taking $G + H$ then identifying $x$ with $y$ .

Tutte: $T_{G * H} = T_G T_H$ .

Magnitude: $\mu_{G * H} = \mu_G + \mu_H - 1$ .
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)$ as a polynomial in $x$ (with $y$ regarded as constant) is $\left|V\right| - 1$ .

Magnitude: yes: it’s $\mu_G(0)$ .
Knows the number of edges?

Tutte: yes: $T_G(2, 2) = 2^{\left|E\right|}$ . (Here and later, I’ll use $E$ for the set of edges of a graph $G$ , and $V$ 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 $q$ in the power series expansion of $\mu_G(q)$ is $-2$ times the number of edges. In other words, $\left|E\right| = -\mu'_G(0)/2$ . (See this comment, and the reply to it, below.)
Discrete graphs Let $G$ be a discrete graph, that is, one with no edges at all.

Tutte: $T_G(x, y) = 1$ .

Magnitude: $\mu_G(q) = \left|V\right|$ .
Forests Let $G$ be a forest, that is, a disjoint union of trees.

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

Magnitude: $\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$ .
Cycles Let $C_n$ be the $n$ -cycle:

Tutte: $T_{C_n}(x, y) = x^{n-1} + x^{n-2} + \cdots + x + y = \frac{x^n - x}{x - 1} + y$

Magnitude: $\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 $n$ is even then $\mu_{C_n}(q) = \frac{n(q - 1)}{(q^{n/2} - 1)(q + 1)}.$ If $n$ is odd then $\mu_{C_n}(q) = \frac{n(q - 1)}{2q^{(n+1)/2} - q - 1}.$
Complete graphs Let $K_n$ be the complete graph on $n$ 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_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).$

Magnitude: $\mu_{K_n}(q) = \frac{n}{1 + (n - 1)q}$ .
Complete bipartite graphs I’ll just do one. Let $K_{2, 3}$ be this graph:

Tutte: $T_{K_{2,3}}(x, y) = x^4 + 2x^3 + 3x^2 + 3x y + y^2 + x + y$ .

Magnitude: $\mu_{K_{2,3}}(q) = \frac{5 - 7q}{(1 + q)(1 - 2q^2)} = 5 - 12q + 22q^2 - 36q^3 + 56q^4 - \cdots$ .
Bull, tadpole, cricket These three graphs all have the same Tutte polynomial and the same magnitude function:

Let $G$ be any one of them.

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

Magnitude: $\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_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.
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.

Tutte: according to Wikipedia, the Petersen graph $P$ has Tutte polynomial $\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: $\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.
Linear codes I’m going to be very sketchy here. (If you want to know more, just say so in the comments.) Let $F$ be a finite field. A linear code over $F$ is simply a linear subspace of $F^n$ , for some $n$ .

Tutte: Every linear code $C$ has a Tutte polynomial $T_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 $C$ is determined by its Tutte polynomial together with the cardinalities of $C$ and $F^n$ .

Magnitude: On the other hand, every linear code can be regarded as a metric space (with the Hamming distance inherited from $F^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 $C$ .

So in the case of linear codes, the Tutte polynomial (plus the cardinalities of $C$ and $F^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 $\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.

What information can be read off from the magnitude function of a graph?
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?
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?
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

$MathML-enabled post (click for more details).$

It occurs to me belatedly that in all the examples I’ve given, the coefficient of $q$ in the power series expansion of $\mu_G(q)$ is $-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

$MathML-enabled post (click for more details).$

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 = 0$ ” and calculating the magnitude function of a graph under that assumption. It comes out as $\left|V\right| - 2\left|E\right|q$ , for a graph $G = (V, E)$ .

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

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

$w_x = 1 - deg(x)q$

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

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

$MathML-enabled post (click for more details).$

Cool stuff! I’m trying to track down what the coefficient of $q^2$ is counting in case $G$ has no loops or multiple edges. In $det Z_G(q)$ , the $q$ -coefficient is always zero, and the $q^2$ -coefficient is $-E$ , so the inverse determinant modulo $q^3$ is $1+E q^2$ . And in $Z_G(q)$ ’s cofactor matrix, there seems to be a $-q^2$ for every pair of non-incident edge and vertex, a $+q^2$ for every pair of edges sharing one vertex, and a $-q^2$ for each pair of vertices a distance of $2$ 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^3$ we have

$\mu_G(q) = (1+E q^2)(V - 2E q + (-E(V-2) + 6\Delta + 2\Lambda')q^2)$

$\mu_G(q) = V - 2E q + (2 E + 6\Delta + 2\Lambda')q^2$ ,

where $\Delta$ is the number of triangles of $G$ 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 ( $\Delta=\Lambda'=0$ ),

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

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

$n$ -cycles for $n\geq 5$ ( $\Delta=\Lambda'=0$ ),

complete graphs $K_n$ ( $\Delta = n(n-1)(n-2)/6, \Lambda'=0$ ),

$K_{2,3}$ ( $\Delta=0, \Lambda'=5$ ),

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

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

Re: Tutte Polynomials and Magnitude Functions

$MathML-enabled post (click for more details).$

Excellent! This would also explain the empirical observation that the coefficient of $q^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^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 $q$ . 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 $x$ and $y$ distance $2$ apart, and two different paths of length $2$ between them, that makes a $4$ -cycle.

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

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

Or equivalently, can we find rational $d_{n, k}$ (independent of $G$ ) such that

$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

$MathML-enabled post (click for more details).$

I was also hoping that the number of “redundant wedges” could be expressed in terms of the number of $4$ -cycles, but what dissuaded me (after wondering why my formulas worked for every one of your example graphs except $K_{2,3}$ ) was that I had missed this fact: if you glue together $n$ wedges at their horns to get $K_{2,n}$ , the number of redundant wedges grows linearly in $n$ (namely, it’s $2n-1$ ) and the number of $4$ -cycles grows quadratically ( $n(n-1)/2$ ). And there are problems going the other way, too: a $4$ -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_4$ and $K_{2,3}$ both have three $4$ -cycles, but the former has no redundant wedges and the latter has $5$ . As far as I know, the number of triangles may be enough to deduce the number of redundant wedges from the number of $4$ -cycles and vice versa, but there’s no fixed linear relation among the three quantities (a $3$ -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

$MathML-enabled post (click for more details).$

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 $G \square H$ is the $\ell^1$ product of the spaces arising from $G$ and $H$ . 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

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

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

I don’t know whether there’s a nice formula for the Tutte polynomial of $G \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

$MathML-enabled post (click for more details).$

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|$ of a subset $X$ of Euclidean space is continuous and defined for every $t\in (0,\infty)$ , but the following plot shows (in red) the magnitude function $|tG|$ of a random graph $G$ , generated by maple, with $101$ vertices and probability $0.1$ that any two given vertices share an edge. (On the $x$ -axis we have $t$ which is $\log q$ .)

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^t$ as your fundamental variable whereas I like to plot semi-logarithmically which means I use $\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

$MathML-enabled post (click for more details).$

Thanks!

Re your last paragraph, I’m thinking algebraically rather than numerically — that is, treating $q$ as a formal variable rather than a real number. (Incidentally, $q$ is $e^{-t}$ , not $e^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 $\mu_G$ in terms of magnitude, we’d define the spread function of a graph $G = (V, E)$ as

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

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

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

$\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 =$ o—o—o

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

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

$\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$ with an offset that changes with period three: $+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

$MathML-enabled post (click for more details).$

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 $\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 $\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 $2$ 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 $G$ is given by $\epsilon_G(q)=\sum_x \frac{1}{\sum_y q^{d(x,y)}}.$

So for each vertex $x$ we get an additive contribution of $\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)$ is the number of vertices a distance exactly $d$ from the vertex $x$ . Adding these altogether we get $\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 $\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^2$ ?

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

Re: Tutte Polynomials and Magnitude Functions

$MathML-enabled post (click for more details).$

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^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

$MathML-enabled post (click for more details).$

In terms of distance-one and distance-two neighbours, the coefficient of $q^2$ in $\epsilon_G(q)$ , the spread function of $G$ , is $\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^2$ in the magnitude of $K_{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 $n$ -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

$MathML-enabled post (click for more details).$

According to Owen, the coefficient of $q^2$ in the magnitude function $\mu_G(q)$ is $2E+6\Delta+2\Lambda'$ and $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 $\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 $G$ . 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 $q$ is about looking at graphs at small scales. Rather, it can be thought of as looking at graphs at large scales: $q=0$ corresponds to $t=+\infty$ . (I realise we are just doing things algebraically and not numerically.) We know that for a finite metric space $X$ we have $\lim_{t\to \infty} |t X|= card(X)$ this is why we have $\mu_G(0)=V$ . So the fact that the first three terms of the magnitude $\mu_G(q)$ and spread $\epsilon_G(q)$ functions coincide for a graph $G$ 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

$MathML-enabled post (click for more details).$

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

$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, 2$ gives the three formulas we already know.

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

$\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 $\mathbf{A}$ containing no nontrivial isomorphisms or idempotents:

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

$MathML-enabled post (click for more details).$

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

$MathML-enabled post (click for more details).$

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

$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 $q$ ) both begin $V-2E q+T q^2$ . If we write $q=e^{-t}$ then we can plot $V-2 E e^{-t}+T e^{-2t}$ with the usual magnitude and spread functions (in terms of $t$ ).

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

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

$MathML-enabled post (click for more details).$

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

$MathML-enabled post (click for more details).$

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)$ is also unaltered by multiple edges and behaves in a very simple way for loops: $T(x,0)=0$ if the graph has a loop. So you might want to look at that part of Tutte. $T(x,0)$ is very closely related to the chromatic polynomial of $G$ ; see here and here.

Third: Let $G$ and $H$ be two graphs with $u_1$ and $v_1$ vertices of $G$ , and $u_2$ and $v_2$ vertices of $H$ . Let $X$ be the graph obtained by gluing $G$ to $H$ with $(u_1, u_2)$ and $(v_1, v_2)$ identified; let $Y$ be the graph obtained by gluing $G$ to $H$ with $(u_1, v_2)$ and $(v_1, u_2)$ identified.

The graphs $X$ and $Y$ 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(G \cap H)$ for $X = 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

$MathML-enabled post (click for more details).$

OK, I just checked the Whitney twist of two random $10$ vertex graphs $G$ and $H$ . They had the same magnitude.

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

Let $X$ be the push out of $G \leftarrow M \rightarrow H$ . Let $Y$ be the similar pushout, but where we twist the map $M \rightarrow H$ so that $u$ gets glued to $v'$ and $v$ to $u'$ .

Do we get $\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

$MathML-enabled post (click for more details).$

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

and

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

$MathML-enabled post (click for more details).$

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\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

$MathML-enabled post (click for more details).$

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)$ , the degree of $T_G(x, y)$ as a polynomial in $x$ (with $y$ thought of as constant) is $\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)$ is also unaltered by multiple edges and behaves in a very simple way for loops: $T(x,0)=0$ if the graph has a loop. So you might want to look at that part of Tutte. $T(x,0)$ is very closely related to the chromatic polynomial of $G$

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

$MathML-enabled post (click for more details).$

“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 $10$ vertices, with edge inclusion probability $0.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 $H$ has a vertex of degree $9$ and $G$ does not. Let $X$ be the result of gluing $1$ and $2$ , in $H$ , to $9$ and $10$ in $G$ . Let $Y$ be the result of gluing $1$ and $2$ in $H$ to $10$ and $9$ in $G$ . Again, $X$ and $Y$ are not isomorphic, because $X$ has a vertex of degree $11$ , and $Y$ does not.

It turns out $X$ and $Y$ have the same magnitude! Specifically, it is $f/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 $G$ and $H$ .

But that isn’t the strangest thing! I computed the vectors $P_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

$MathML-enabled post (click for more details).$

That’s strange and very interesting, especially that

I cannot find any relation between this rational function and the magnitudes of $G$ and $H$ .

Can you tell me the vectors

$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 $X$ and $Y$ .

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 $\mu_X$ and $\mu_Y$ in terms of $\mu_G$ and $\mu_H$ .

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

Re: Tutte Polynomials and Magnitude Functions

$MathML-enabled post (click for more details).$

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

They are precisely the same. All the terms have the same denominator, which is the polynomial $g$ 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

$MathML-enabled post (click for more details).$

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

$MathML-enabled post (click for more details).$

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

The graph $X$ is formed from $G$ and $H$ by gluing vertex 9 of $G$ to vertex 1 of $H$ (making a new vertex $\{9, 1\}$ ) and gluing vertex 10 of $G$ to vertex 2 of $H$ (making a new vertex $\{10, 2\}$ ). So the 18 vertices of $X$ are the vertices $1, \ldots, 8$ of $G$ , the vertices $3, \ldots, 10$ of $H$ , and these two new vertices, $\{9, 1\}$ and $\{10, 2\}$ .

The graph $Y$ is formed from $G$ and $H$ by gluing vertex 9 of $G$ to vertex 2 of $H$ (making a new vertex $\{9, 2\}$ ) and gluing vertex 10 of $G$ to vertex 1 of $H$ (making a new vertex $\{10, 1\}$ ). So the 18 vertices of $Y$ are the vertices $1, \ldots, 8$ of $G$ , the vertices $3, \ldots, 10$ of $H$ , and these two new vertices, $\{9, 2\}$ and $\{10, 1\}$ .

When you say that the weighting $w_X$ on $X$ is the same as the weighting $w_Y$ of $Y$ , presumably that means for a start that $w_X$ and $w_Y$ agree on the vertices $1, \ldots, 8$ of $G$ and the vertices $3, \ldots, 10$ of $H$ . But are you saying that

$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\}) \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\})$ , 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

$MathML-enabled post (click for more details).$

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 $G$ and $H$ both be this graph: o—o—o. Choose two adjacent vertices $u$ and $v$ of $G$ , and two adjacent vertices $u'$ and $v'$ of $H$ . Glue $G$ and $H$ together in the usual two ways: either glue $u$ to $u'$ and $v$ to $v'$ , or glue $u$ to $v'$ and $v$ to $u'$ . One of the results, $X$ , is a 4-vertex graph shaped like a T. The other, $Y$ , is o—o—o—o.

Then $X$ and $Y$ 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

$MathML-enabled post (click for more details).$

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

$MathML-enabled post (click for more details).$

Tom asked David:

When you say that the weighting $w_X$ on $X$ is the same as the weighting $w_Y$ of $Y$ , presumably that means for a start that $w_X$ and $w_Y$ agree on the vertices $1,\dots,8$ of $G$ and the vertices $3,\dots,10$ of $H$ .

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\}) \quad \text{and} \quad w_X(\{10, 2\}) = w_Y(\{10, 1\})$ or that $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 $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\})$ which gives that $X$ and $Y$ have the same magnitude.

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

$MathML-enabled post (click for more details).$

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

$MathML-enabled post (click for more details).$

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

Take the complete graph on five vertices and remove the edges $(1,2)$ and $(2,3)$ . Call this $G$ then take the Whitney twist pair of $G$ with itself using vertices $1$ and $2$ on both copies of $G$ . 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 $G$ and $H$ each with a distinguished edge, say $e_G$ and $e_H$ , then we can form the Whitney twist pair using the end-points of $e_G$ and $e_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

$MathML-enabled post (click for more details).$

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 $G$ to a single vertex of $H$ to form $X$ , then $\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

$MathML-enabled post (click for more details).$

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 $K$ , $G$ and $H$ , and isometries

$G \longleftarrow K \longrightarrow H.$

Suppose that the image of $K$ in $G$ has the following convexity property: if $x, y, z \in G$ with $d(x, y) + d(y, z) = d(x, z)$ , and $x$ and $z$ both belong to the image of $K$ , then so does $y$ . Suppose the same is true of the image of $K$ in $H$ .

Here $G +_K H$ is the pushout.

But maybe Simon can immediately defeat this conjecture. Simon, you say you’ve tried hundreds of examples where $K$ is the graph consisting of a single edge. Is it the case in all of them that the magnitude of the glued graph is $\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

$MathML-enabled post (click for more details).$

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 $(\mathbb{N} \cup \{\infty\}, \geq, 0, +)$ , just as a metric space is a category enriched in $([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 $X$ is geodesic if for all $x, y \in X$ there exists an isometry $\gamma\colon [0, d(x, y)] \to X$ such that $\gamma(0) = x$ and $\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 $n \in \mathbb{N}$ , write $[n]$ for the graph

0 — 1 — 2 — $\cdots$ — $n$ .

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

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

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

$MathML-enabled post (click for more details).$

Of course the inclusion-exclusion formula does at least hold for trees, which you can nicely characterize as those graphs for which each $x$ and $y$ 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

$MathML-enabled post (click for more details).$

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

$MathML-enabled post (click for more details).$

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 $I$ be the connected graph with two vertices, the triangle $T$ be the complete graph on three vertices and let the braced diamond $D$ be the four vertex graph obtained by glueing two triangles along a subgraph $I$ .

Then $\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^2-12q^3+46q^4+O(q^5)\neq 0.$

Note that the inclusion-exclusion formula will work mod $q^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 $T$ onto a braced diamond $D$ along an edge in two different ways. These give rise to different graphs with different magnitudes, namely $5 - 14 q + 36 q^2 - 94 q^3 + 246 q^4 + O(q^5)$ and $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

$MathML-enabled post (click for more details).$

Hmph. Thanks.

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

David’s Whitney twist example with a couple of random 10-vertex graphs. The vertices we’re gluing along are different distances apart in the two original graphs.
Simon’s hundreds of Whitney twist examples, gluing along a single edge. Here, the vertices we’re gluing along are the same distance apart in the two original graphs (namely, 1).

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

$MathML-enabled post (click for more details).$

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

$MathML-enabled post (click for more details).$

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

$MathML-enabled post (click for more details).$

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

$MathML-enabled post (click for more details).$

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 $G$ and a subgraph $K$ whose induced metric is the same as the subspace metric from $G$ . (Again, this is a kind of convexity condition on $K$ .) Say that $G$ projects to $K$ if for all $g \in G$ there exists $\pi(g) \in K$ such that for all $k \in K$ ,

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

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

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

$\mu_{G +_K H} = \mu_G + \mu_H - \mu_K.$

Special case: $K$ 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 $K$ is the same as the subspace metric inherited from any graph $G$ it’s embedded in. When does $G$ project to $K$ ? Exactly when $G$ contains no vertices equidistant from the two vertices of $K$ . So if I’m not mistaken, we have:

Theorem Take a graph $G$ with distinguished vertices $u$ and $v$ , joined by an edge, such that no vertex of $G$ equidistant from $u$ and $v$ . Take $H$ , $u'$ and $v'$ subject to the same conditions. Let $J$ be the graph formed from the disjoint union of $G$ and $H$ by identifying the edge $u v$ with the edge $u' v'$ (either way round). Then

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

$MathML-enabled post (click for more details).$

Nice! This ties in nicely with the fact that the quadratic “correction term” $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 $G$ or $H$ 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

$MathML-enabled post (click for more details).$

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

Theorem Let $X \longleftarrow Z \longrightarrow Y$ be distance-preserving maps of finite metric spaces. Suppose that $X$ projects to the image of $Z$ . (We don’t suppose that $Y$ projects to the image of $Z$ .) If $X$ and $Y$ have magnitude then so do $Z$ and the pushout $X +_Z Y$ , and $\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 $X \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 $G$ , 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

$MathML-enabled post (click for more details).$

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 $\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^\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 $X\xrightarrow{g} Z \xleftarrow{f} Y$ such as either $f$ or $g$ 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

$MathML-enabled post (click for more details).$

David S’s example falls into my class of examples (or rather, my class of examples generalizes his example). He has edge $\{10,9\}$ in $G$ and so in $X$ and $Y$ 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

$MathML-enabled post (click for more details).$

Oh I see. Thanks. The point is that although there isn’t an edge in $H$ 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 $G$ and $H$ — 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

$MathML-enabled post (click for more details).$

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 $G$ and $H$ with a specified edge in each of them then there are two pushouts $X$ and $Y$ we can form, depending on how we identify the edges. We know that the constant and linear terms in the magnitude of $X$ and $Y$ 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 $X$ and $Y$ 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

$MathML-enabled post (click for more details).$

Okay. I can tell you what the quadratic term is when you glue along an edge. Suppose $\{a,b\}$ is an edge in $G$ and $\{c,d\}$ is an edge in $H$ . Let $T$ denote the coefficient of $q^2$ in the magnitude as above (this conflicts with $T$ 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 +_I H)$ of $G$ glued to $H$ along the specified edges, would be given by $T(G)+T(H)-T(I)$ , i.e. by $T(G)+T(H)-2$ . However, it is actually given by $T(G)+T(H)-2+2N_1(a,b)N_1(c,d)$ where $N_1(a,b)$ is the number of vertices in $G$ which are distance one from both $a$ and $b$ , this can be thought of as the number of triangles in $G$ with base $\{a,b\}$ , and similarly for $N_1(c,d)$ .

Note that this does not depend on whether $a$ is glued to $c$ and $b$ is glued to $d$ 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 $36$ and $38$ 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

$MathML-enabled post (click for more details).$

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

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

If we could make a more precise statement about the relation between $Z_G$ and $P_G$ , we could probably make a more precise relation between the magnitude of $G$ and $|\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

$MathML-enabled post (click for more details).$

OK, so for vertices $i$ and $j$ ,

$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 $G$ , there are three different matrices whose magnitude we might wish to consider:

$P_G(q)$
$Z_G(q)$ (whose magnitude is the magnitude of the metric space $G$ )
the adjacency matrix $A_G$ , or perhaps $q 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

$MathML-enabled post (click for more details).$

Here, maybe, is another piece of this puzzle.

As you noted, $(A^d)_{i j}$ is the number of paths of length $d$ from $i$ to $j$ . Similarly, $((I+A)^d)_{i j}$ is the number of paths of length $\le d$ from $i$ to $j$ . So let’s define, for a matrix $M$ , a matrix $\Gamma(M)$ whose $i,j$ entry is $1$ if $m_{i j} \neq 0$ , and $0$ otherwise. (This has a standard name which I’ve forgotten, and $\Gamma$ may or may not be a standard notation for it.) Then $\Gamma((I+A)^d)$ tells you exactly which vertices have distance $\le d$ from each other. Therefore $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) = (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)$ is a somewhat different sort of “truncation” of $Q_G(q)$ . To first order in $q$ , $Q_G(q)$ and $P_G(q)$ are both $I + q A$ .

It may be worth noting that your example relating to clique numbers was to do with reflexive graphs, so maybe $I + 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

$MathML-enabled post (click for more details).$

Actually, $(I+A)^d$ isn’t exactly what I said (paths of different lengths get weighted differently), but $\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

$MathML-enabled post (click for more details).$

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 $f$ and $g$ over $\mathbb{Q}$ , we can talk about the degree of the rational function $f/g$ in at least two senses:

The “asymptotic degree”, $deg(f) - deg(g)$ . When $q$ is large, $f(q)/g(q)$ behaves roughly like $q^d$ , where $d$ is the asymptotic degree.
The topological degree, $max\{deg(f), deg(g)\}$ (where $f$ and $g$ have had any common factors removed). This is the degree of $f/g$ as an endomorphism of the Riemann sphere $\mathbb{C} \cup \{\infty\}$ .

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

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

$MathML-enabled post (click for more details).$

An easy observation: if $G$ is homogeneous (meaning that its automorphism group acts transitively on vertices) then the topological degree is the diameter of $G$ , 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

$MathML-enabled post (click for more details).$

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 $k$ of functions $(0,\infty) \to \mathbb{R}$ defined on a cofinite set and modulo equality on cofinite sets, and the monoid homomorphism $\vert\cdot\vert :([0,\infty], +) \to (k,\cdot)$ given by $\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

$MathML-enabled post (click for more details).$

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

$MathML-enabled post (click for more details).$

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

$MathML-enabled post (click for more details).$

Mark wrote:

I wonder if it would be enlightening to think of magnitude in general as built in terms of the rig $k$ of functions $(0, \infty) \to \mathbb{R}$ defined on a cofinite set and modulo equality on cofinite sets, and the monoid homomorphism $|\cdot|: ([0, \infty], +) \to (k, \cdot)$ given by $|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^{-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, \infty) \to \mathbb{R}$ consisting of finite $\mathbb{R}$ -linear combinations of functions of the form $e^{-t x}$ ( $t \geq 0$ ). This is an integral domain (e.g. because those basic functions are linearly independent), so it has a field of fractions $K$ . It’s a subrig of Mark’s $k$ , and is analogous to the $\mathbb{Q}(q)$ of the graph case. I don’t know whether $K$ 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

$MathML-enabled post (click for more details).$

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

$MathML-enabled post (click for more details).$

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_5$ , the $5$ -cycle, they would have found

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

$MathML-enabled post (click for more details).$

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

Looking forward to your paper with Richard coming out.

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

The n-Category Café

Skip to the Main Content

April 16, 2013