Hostname: page-component-745bb68f8f-v2bm5 Total loading time: 0 Render date: 2025-02-10T21:14:55.273Z Has data issue: false hasContentIssue false
  • English
  • Français

The magnitude of a graph

Published online by Cambridge University Press:  27 November 2017

TOM LEINSTER
TOM LEINSTER*
Affiliation:
School of Mathematics, University of Edinburgh, James Clerk Maxwell Building, The King's Buildings, Peter Guthrie Tait Road, Edinburgh EH9 3FD. e-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

The magnitude of a graph is one of a family of cardinality-like invariants extending across mathematics; it is a cousin to Euler characteristic and geometric measure. Among its cardinality-like properties are multiplicativity with respect to cartesian product and an inclusion-exclusion formula for the magnitude of a union. Formally, the magnitude of a graph is both a rational function over ℚ and a power series over ℤ. It shares features with one of the most important of all graph invariants, the Tutte polynomial; for instance, magnitude is invariant under Whitney twists when the points of identification are adjacent. Nevertheless, the magnitude of a graph is not determined by its Tutte polynomial, nor even by its cycle matroid, and it therefore carries information that they do not.

Type
Research Article
Information
Mathematical Proceedings of the Cambridge Philosophical Society , Volume 166 , Issue 2 , March 2019 , pp. 247 - 264
Copyright
Copyright © Cambridge Philosophical Society 2017 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1] Barceló, J. A. and Carbery, A. On the magnitudes of compact sets in Euclidean spaces. Amer. J. Math., in press (2015).Google Scholar
[2] Chuang, J., King, A. and Leinster, T. On the magnitude of a finite dimensional algebra. Theory Appl. Categ. 31 (2016), 63–72.Google Scholar
[3] Gimperlein, H. and Goffeng, M. On the magnitude function of domains in Euclidean space. arXiv:1706.06839 (2017).Google Scholar
[4] Godsil, C. and Royle, G. Algebraic Graph Theory (Springer, New York, 2001).Google Scholar
[5] Hepworth, R. and Willerton, S. Categorifying the magnitude of a graph. Homology, Homotopy Appl. 19 (2017), 31–60.Google Scholar
[6] Kelly, G. M. Basic Concepts of Enriched Category Theory. London Mathematical Society Lecture Note Series. vol. 64 (Cambridge University Press, Cambridge, 1982). Also Reprints in Theory and Applications of Categories 10 (2005), 1–136.Google Scholar
[7] Khovanov, M. A categorification of the Jones polynomial. Duke Math. J. 101 (2000), 359–426.Google Scholar
[8] Klain, D. A. and Rota, G.–C.. Introduction to Geometric Probability. Lezioni Lincee. (Cambridge University Press, Cambridge, 1997).Google Scholar
[9] Leinster, T. The Euler characteristic of a category. Documenta Math. 13 (2008), 21–49.Google Scholar
[10] Leinster, T. The magnitude of metric spaces. Documenta Math. 18 (2013), 857–905.Google Scholar
[11] Leinster, T. Tutte polynomials and magnitude functions. Post at The n-Category Café, http://golem.ph.utexas.edu/category/2013/04/tutte_polynomials_and_magnitud.html (2013).Google Scholar
[12] Leinster, T. and Meckes, M. Maximizing diversity in biology and beyond. Entropy 18 (88), (2016).Google Scholar
[13] Leinster, T. and Willerton, S. On the asymptotic magnitude of subsets of Euclidean space. Geome. Dedicata 164 (2013), 287–310.Google Scholar
[14] Meckes, M. W. Positive definite metric spaces. Positivity 17 (2013), 733–757.Google Scholar
[15] Meckes, M. W. Re: Tutte polynomials and magnitude functions. Comment at [11] (2013).Google Scholar
[16] Meckes, M. W. Magnitude, diversity, capacities, and dimensions of metric spaces. Potential Anal. 42 (2015), 549–572.Google Scholar
[17] Oxley, J. G. Matroid Theory (Oxford University Press, Oxford, 1992).Google Scholar
[18] Rota, G.–C. On the foundations of combinatorial theory I: theory of Möbius functions. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete 2 (1964), 340–368.Google Scholar
[19] Rota, G.–C. Indiscrete Thoughts (Birkhäuser, Boston, 1997).Google Scholar
[20] Schanuel, S. H. Negative sets have Euler characteristic and dimension. In Category Theory (Como, 1990) Lecture Notes in Math. 1488, pages 379–385. (Springer, Berlin, 1991).Google Scholar
[21] Speyer, D. Re: Tutte polynomials and magnitude functions. Comments at [11] (2013).Google Scholar
[22] Stanley, R. P. Enumerative Combinatorics, Vol. 1. Cambridge Stud. Adv. Math. 49 (Cambridge University Press, Cambridge, 1997).Google Scholar
[23] Tutte, W. T. A contribution to the theory of chromatic polynomials. Canad. J. Math. 6 (1954), 80–91.Google Scholar
[24] Weil, A. A 1940 letter of André Weil on analogy in mathematics. Not. Amer. Math. Soc. 52 (3) (2005), 334–341.Google Scholar
[25] Whitney, H. 2-isomorphic graphs. Amer. J. Math. 55 (1933), 245–254.Google Scholar
[26] Willerton, S. Re: Tutte polynomials and magnitude functions. Comments at [11] (2013).Google Scholar