Homology, Homotopy and Applications

Volume 19 (2017)

Number 2

Categorifying the magnitude of a graph

Pages: 31 – 60

DOI: https://dx.doi.org/10.4310/HHA.2017.v19.n2.a3

Authors

Richard Hepworth (Institute of Mathematics, University of Aberdeen, Scotland, United Kingdom)

Simon Willerton (School of Mathematics and Statistics, Hicks Building, University of Sheffield, United Kingdom)

Abstract

The magnitude of a graph can be thought of as an integer power series associated to a graph; Leinster introduced it using his idea of magnitude of a metric space. Here we introduce a bigraded homology theory for graphs which has the magnitude as its graded Euler characteristic. This is a categorification of the magnitude in the same spirit as Khovanov homology is a categorification of the Jones polynomial. We show how properties of magnitude proved by Leinster categorify to properties such as a Künneth Theorem and a Mayer–Vietoris Theorem. We prove that joins of graphs have their homology supported on the diagonal. Finally, we give various computer calculated examples.

Keywords

magnitude, graph, categorification

2010 Mathematics Subject Classification

05C31, 55N35

Received 15 July 2016

Published 2 August 2017