Graph theoretic properties of Speyer's matroid polynomial $g_M(t)$

Abstract

We prove relations between the number of $k$-connected components of a graph, Crapo's invariant ${\hat{I}}^2(M)$ of a matroid, and Speyer's polynomial $g_M(t)$. These yield a simple interpretation of $g_M^{\prime }(-1)$ when $M$ is graphic or cographic. Furthermore, we improve Ferroni's algorithm to compute $g_M(t)$ and provide an implementation and an extensive data set. These calculations reveal a large number of graph theoretic constraints on the second derivative $g_M^{\prime \prime }(-1)$, which we thus advertise as an intriguing new invariant of graphs. We also propose a relation between the flow polynomial and $g_M^{\prime \prime }(0)$ for cubic graphs.

56 pages, 8 tables, 17 figures, associated with open-source code and a data set