### The Magnitude of a Graph

#### Posted by Tom Leinster

I’ve just arXived a new paper about a new invariant, The magnitude of a graph. Much of the development of this invariant has taken place at this blog, with two previous posts and crucial contributions from David Speyer and Simon Willerton. Your comments, critical or otherwise, would be very welcome.

Magnitude seems to be orthogonal to other graph invariants. You can’t derive from it such classic invariants as the Tutte polynomial or the chromatic number, nor the girth nor the clique number nor even the number of connected components. And conversely, you can’t derive the magnitude from these or any other well-known graph invariants. Apparently, it captures information of a different kind.

Its most appealing characteristic is that it behaves like cardinality. It’s multiplicative with respect to cartesian product, additive with respect to disjoint union, and obeys a restricted version of the inclusion-exclusion principle. And it also behaves a bit like the Tutte polynomial. For instance, it’s often invariant under Whitney twists — though not always, as I’ll explain.

That it behaves like cardinality is no surprise, given its origins.

Steve Schanuel taught us that the Euler characteristic of a space should be thought of as analogous to the cardinality of a set. There is a notion of the Euler characteristic of a category, closely related to other forms of Euler characteristic. This notion can be generalized to enriched categories, then specialized to categories enriched in the poset $(\mathbb{N}, \geq)$, seen as a monoidal category via addition. Any graph gives rise to an $\mathbb{N}$-enriched category, the objects being the vertices and the homs being distances in the graph. So, we get an invariant of graphs — and that’s what’s called magnitude.

That’s a highly condensed account, and you can find out more by following the links, but let me skip all that and tell you the end result, which is completely concrete.

The magnitude $\# G$ of a graph $G$ is a rational function over $\mathbb{Q}$ — the ratio of two polynomials with integer coefficients. It can also be expressed as a power series over $\mathbb{Z}$. For example, the graph

has magnitude

$\frac{5 + 5q - 4q^2}{(1 + q)(1 + 2q)} = 5 - 10q + 16q^2 - 28q^3 + 52q^4 - 100q^5 + \ldots.$

Here $q$ is just a formal variable.

The definition goes like this. Take a graph $G$. Let $Z$ be the square matrix whose rows and columns are indexed by the vertices of $G$, and whose entries are given by

$Z(x, y) = q^{d(x, y)}$

for each pair of vertices $x$ and $y$. Here $d(x, y)$ is the distance between $x$ and $y$ in the graph (and by convention, $q^\infty = 0$). It turns out that $Z$ is invertible over both the field $\mathbb{Q}(q)$ of rational functions and the ring $\mathbb{Z}[q]$ of power series. The **magnitude** of $G$ is the sum of all the entries of its inverse.

I know of no direct graph-theoretic motivation for this definition. Frankly, it looks odd. The real motivation is that it’s part of a large family of related invariants, including not only cardinality and various types of Euler characteristic, but also metric dimension, maximum entropy, and, conjecturally, geometric measures like volume, surface area and perimeter. From that point of view, it would be odd if graph magnitude *wasn’t* important.

The paper has two main theorems. First, magnitude obeys an inclusion-exclusion principle: when $G$ and $H$ are subgraphs of some larger graph, and certain further conditions hold,

$\# (G \cup H) = \#G + \#H - \#(G \cap H)$

(Theorem 4.9). I was frustrated by having to impose those “further conditions”, because it meant that magnitude didn’t behave entirely like cardinality. But then I figured out that *no nontrivial graph invariant behaves entirely like cardinality* (Lemma 4.1).

The second main theorem was conjectured by Simon. Take a graph with two distinct vertices distinguished, and another graph with two distinct vertices distinguished. Glue them together by pairing up the distinguished vertices. There are two different ways you can do this, depending on how you do the pairing, and the two resulting graphs are said to differ by a Whitney twist.

David Speyer pointed out that (as all graph theorists know) the Tutte polynomial is invariant under Whitney twists, so if magnitude is a specialization of the Tutte polynomial, it had better be invariant too. Then David got his computer to randomly generate a couple of 18-vertex graphs differing by a Whitney twist, and lo and behold, their magnitudes were equal. That magnitude was a rational function of degree 23 whose coefficients were integers of up to 5 decimal digits, so it was *highly* unlikely that this happened by chance.

So, when Simon found an example showing that magnitude *isn’t* invariant under Whitney twists, it came as a considerable surprise. What’s going on?

Well, Simon immediately conjectured that you get invariance *only when the two points of identification are joined by an edge* in one of the original two graphs. That turns out to be true — and that’s the second theorem.

The apparently implausible coincidence in David’s experiment can therefore be explained as follows. He generated two 10-vertex graphs $G$ and $H$, putting an edge between each pair of vertices with probability $0.4$. He then joined them together in two ways, giving two 18-vertex graphs $X$ and $Y$ differing by a Whitney twist. The second theorem applies if $X$ (or equivalently $Y$) has an edge between the two points of identification, and the probability that this happens is $1 - (1 - 0.4)^2 = 0.64$. So, it was more likely than not that he’d get what he got.

## Re: The Magnitude of a Graph

Incidentally, the grammar of the title of the paper is dedicated, with affection, to John Baez. When I finished my paper The magnitude of metric spaces, John wrote to me specifically to complain that I should have called it “The magnitude of a metric space”, teasing me with outrageously unfair comparisons between my actual title and “The Sound of Musics”, “The Joy of Sexes”, and so on. I replied not only in kind (making up an undergraduate textbook called “The Solution of an Ordinary Differential Equation”), but also by Latexing a retitled version of the paper especially for him. So: John, this title’s for you.