Asymptotic Resurgence of facet ideals of graphic matroids in Sage

Load functions to compute skew Waldschmidt constant and asymptotic resurgence

Click the "Evaluate" button below to define the functions in the file Asymptotic resurgence of facet ideal of matroid .

A non-Hamiltonian outlier

The following graph is Example 6.1 in "Asymptotic resurgence of facet ideals of graphic matroids." It is the uniqe minimal non-Hamiltonian graph on nine vertices so that the asymptotic resurgence of its facet ideal achieves the upper bound of $2-2/9$, $9$ being the number of vertices.

We verify that the asymptotic resurgence of the facet ideal of the graphic matroid of $G$ is $2-2/9$.

Petersen Graph

The Petersen graph is non-Hamiltonian, but it is a regular graph. By Theorem 5.5 in "Asymptotic resurgence of facet ideals of graphic matroids", the asymptotic resurgence of the facet ideal of the graphic matroid of the Petersen graph is $2-\frac{2}{10}$.

The following computation will probably time out the online Sage server.

A three-regular graph with edge connectivity two

The following graph is Example 6.5 in "Asymptotic resurgence of facet ideals of graphic matroids."

The computation of the asymptotic resurgence of the facet ideal of the graphic matroid of $G$ is 9/5, verifying the claim in Example 6.5. The following code computes this number, but it will likely time out the online Sage server.

The asymptotic resurgence of non-Hamiltonian graphs

If $G$ is a Hamiltonian graph on $n$ vertices, then Theorem 5.5 in "Asymptotic resurgence of facet ideals of graphic matroids" shows that the asymptotic resurgence of the facet ideal of the graphic matroid of $G$ is $2-2/n$. If $G$ is not Hamiltonian, then it follows from Theorem 4.6 and Theorem 5.5 of the same paper that $$ 2-\frac{2}{c}\le \widehat{\rho}(I(M(G)))\le 2-\frac{2}{n}, $$ where $c$ is the circumference of $G$ and $n$ is the number of vertices of $G$. In Question 7.2 we ask if the asymptotic resurgence always achieves one of the bounds above, and we verified that this is indeed the case for graphs on up to nine vertices. Here we illustrate the code to run successively for $n=1,\ldots,9$ to verify this. We rely on Theorem 2.5 of "Asymptotic resurgence of facet ideals of graphic matroids", which states that $$ \widehat{\rho}(I(M))=\max\left\lbrace \frac{\text{rank}(M)}{\widehat{\alpha}(I(M))}, \widehat{\rho}_{c,1}(I(M))\right\rbrace, $$ where $$ \widehat{\rho}_{c,1}(I(M))=\max_{F\in \mathcal{L}_1(M)\setminus \{E\}}\{\widehat{\rho}(I(M/F)) $$ and $\mathcal{L}_1(M)$ is the set of rank one flats of $M$. Now suppose we know that every simple $2$-connected graph $H$ on at most $n$ vertices satisfies $$ \widehat{\rho}(I(M(H)))=2-\frac{2}{c(H)}, $$ where $c(H)$ is the circumference of $H$. If $G$ is a graph on $n+1$ vertices and $G$ is Hamiltonian, then the asymptotic resurgence of the facet ideal of the matroid of $G$ is $2-2/(n+1)=2-2/c$, where $c$ is the circumference of $G$, by Theorem 5.5. Now suppose $G$ is not Hamiltonian. The rank one flats of the matroid of $G$ correspond to edges and its contractions along rank one flats yield simple (although not necessarily $2$-connected) graphs on $n$ vertices (once simplified - which preserves the asymptotic resurgence by Theorem 3.2). Since the asymptotic resurgence of the facet ideal of a matroid is the maximum of the asymptotic resurgences of the facet ideals of its connected components (Theorem 3.3), we have that $\widehat{\rho}_{c,1}(I(M))=2-\frac{2}{c_m}$, where $c_m$ is the maximum circumference of a contraction of $G$. Since $G$ is not Hamiltonian, there is an edge whose contraction retains the circumference of $G$, so $c_m=c(G)$. Thus, by Theorem 2.5, we have $$ \widehat{\rho}(I(M(G)))=\max\left\lbrace \frac{\text{rank}(M(G))}{\widehat{\alpha}(I(M(G)))}, 2-\frac{2}{c(G)}\right\rbrace=\max\left\lbrace \frac{n}{\widehat{\alpha}(I(M(G)))}, 2-\frac{2}{c(G)}\right\rbrace $$ We can use this observation to inductively verify that, for every simple 2-connected graph $G$ on $n$ vertices, where $n\le 8$, $$ \widehat{\rho}(I(M(G)))=2-\frac{2}{c(G)}. $$ Furthermore, there are only four non-Hamiltonian simple graphs on nine vertices that satisfy $$ \widehat{\rho}(I(M(G)))=2-\frac{2}{9}. $$ A simple graph on three vertices with at least one edge is either a tree, in which case $I(M(G))$ is principal with $\widehat{\rho}(I(M(G)))=1$, or a (Hamiltonian) three-cycle, in which case $\widehat{\rho}(I(M(G)))=2-2/3=4/3$. So we begin the inductive computation at four vertices.

Since there are no two-connected simple graphs on four vertices that are not Hamiltonian, $\widehat{\rho}(I(M(G)))=2-\frac{2}{c(G)}$ for every such graph $G$.

There are only two non-Hamiltonian two-connected simple graphs on five vertices. We verify that $4/\widehat{\alpha}(I(M(G)))\le 2-\frac{2}{c(G)}$ and thus $\widehat{\rho}(I(M(G)))=2-\frac{2}{c(G)}$ for each of these.

There are eight non-Hamiltonian two-connected simple graphs on six vertices. We verify that $5/\widehat{\alpha}(I(M(G)))\le 2-\frac{2}{c(G)}$ and thus $\widehat{\rho}(I(M(G)))=2-\frac{2}{c(G)}$ for each of these.

There are 85 non-Hamiltonian two-connected simple graphs on seven vertices. We verify that $6/\widehat{\alpha}(I(M(G)))\le 2-\frac{2}{c(G)}$ and thus $\widehat{\rho}(I(M(G)))=2-\frac{2}{c(G)}$ for each of these.

There are 927 non-Hamiltonian two-connected simple graphs on eight vertices. We verify that $7/\widehat{\alpha}(I(M(G)))\le 2-\frac{2}{c(G)}$ and thus $\widehat{\rho}(I(M(G)))=2-\frac{2}{c(G)}$ for each of these.

There are 16983 non-Hamiltonian two-connected simple graphs on nine vertices. We verify that $8/\widehat{\alpha}(I(M(G)))\le 2-\frac{2}{c(G)}$ for all but four of these.