Weak maps and the Tutte polynomial

Christine Cho and James Oxley · 2025

Read Weak maps and the Tutte polynomial by Christine Cho and James Oxley (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-15606.txt.

Introduction

Christine Cho and James Oxley prove a sharp rule in pure math in twenty twenty-five. They study two matroids linked by a weak map that keeps rank the same. For all plus values of the two inputs, the first matroid has a Tutte count at least as large as the second. That holds if and only if a short sum rule holds or the two matroids are the same. The proof builds on past work by Lucas. The pair also draw out results that flow from the rule.

Catalog record

CREATORChristine Cho and James Oxley
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE26 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-15606

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Weak maps and the Tutte polynomial Christine Cho and James Oxley Abstract . Let M M and N N be matroids such that N N is the image of M M under a rank-preserving weak map. Generalizing results of Lucas, we prove that, for x x and y y positive, T ⁡ ( M , x , y ) ≥ T ⁡ ( N , x , y ) T(M;x,y)\geq T(N;x,y) if and only if x + y ≥ x ​ y x+y\geq xy or M ≅ N M\cong N . We give a number of consequences of this result. 1991 Mathematics Subject Classification 05B35 1. Introduction Terminology and notation used here will follow [ 7 ] unless otherwise stated. Given two rank- r matroids M and N , a bijective map from E(M) to E(N) is a rank-preserving weak map if every basis of N is the image of a basis of M . We write M\xrightarrow{rp}N if N is a rank-preserving weak-map image of M . The following theorem of Lucas [ 6 ] shows that the numbers of bases, independent sets, and spanning sets of M are greater than the corresponding numbers for N if M\xrightarrow{rp}N . Note that T(M;1,1) , T(M;2,1) , and T(M;1,2) count the numbers of bases, independent sets, and spanning sets of M , respectively, where T(M;x,y) is the Tutte polynomial of M . Theorem 1 . If M\not\cong N and M\xrightarrow{rp}N , then (i) T(M;1,1)>T(N;1,1) ; (ii) T(M;2,1)>T(N;2,1) ; (iii) T(M;1,2)>T(N;1,2) ; (iv) T(M;x,0)\geq T(N;x,0) for all x>0 unless M has a loop; (v) T(M;0,y)\geq T(N;0,y) for all y>0 unless M has a coloop. The main result of the paper is the following generalization of the last theorem. Theorem 2 . Let x and y be positive real numbers. Let M and N be matroids such that there is a rank-preserving weak map from M to N . Then T(M;x,y)\geq T(N;x,y) if and only if x+y\geq xy or M\cong N . Moreover, if M\not\cong N , then T(M;x,y)>T(N;x,y) if and only if x+y>xy . Jaeger, Vertigan, and Welsh [ 5 ] proved that the problem of evaluating the Tutte polynomial of a graphic matroid at a point (x,y) in the first quadrant of the real plane is #P-hard unless x+y=xy or (x,y)=(1,1) . Evidently x+y=xy if and only if (x,y) is a point on the hyperbola H_{1} defined by the equation (x-1)(y-1)=1 . It is straightforward to prove that T(M;x,y)=(x-1)^{r(M)}y^{|E|} for all (x,y)\in H_{1} . Therefore, for any two matroids M and N that have the same rank and the same ground set, T(M;x,y)=T(N;x,y) for all (x,y)\in H_{1} , that is, for all (x,y) for which x+y=xy . Theorem 2 is summarized in the following figure. 2 2 x+y=xy x y T(M;x,y)>T(N;x,y) T(M;x,y)=T(N;x,y) T(M;x,y)<T(N;x,y) Figure 1 . A summary of Theorem 2 . x_{1} x_{2} x_{4} x_{3} x_{3}^{\prime} x_{5} x_{6} Figure 2 . A rank-3 matroid M . Let f and g be distinct elements in a matroid M . The element f is freer than the element g if g is contained in the closure of every circuit containing f . For example, in the rank-3 matroid M for which a geometric representation is shown in Figure 2 , the element x_{6} is free , that is, every circuit containing x_{6} is spanning. Hence x_{6} is freer than every element in E(M)-\{x_{6}\} . The element x_{1} is freer than both x_{3} and x_{3}^{\prime} . Since \{x_{3},x_{3}^{\prime}\} is a parallel class, it is straightforward to see that x_{3} is freer than x_{3}^{\prime} , and x_{3}^{\prime} is freer than x_{3} . Similarly, x_{1} is freer than x_{2} , and x_{2} is freer than x_{1} . By contrast, although x_{1} and x_{5} are symmetric in M , neither is freer than the other. As a consequence of Theorem 2 , we deduce that if f is freer than g in a matroid M , then the numbers of bases, circuits, and hyperplanes of M containing f are at least as large as the corresponding numbers of sets containing g . The next section presents some preliminaries. The main result is proved in Section 3. The last section contains consequences of the main theorem. 2. Preliminaries The nullity of a matroid M is equal to |E(M)|-r(M) . For matroids M and N , a bijection \varphi:E(M)\to E(N) is a weak map if \varphi^{-1}(I)\in\mathcal{I}(M) whenever I\in\mathcal{I}(N) . If r(M)=r(N) , then \varphi is a rank-preserving weak map from M to N . Although it is not required that a weak map be bijective, we will only consider bijective weak maps. Such maps have the following attractive property (see, for example, [ 7 , Corollary 7.3.13] ). Lemma 3 . If \varphi:M\to N is a rank-preserving weak map from M to N , then \varphi is a rank-preserving weak map from M^{*} to N^{*} . For a matroid M with ground set E , the Tutte polynomial T(M;x,y) of M is defined by T(M;x,y)=\displaystyle\sum_{A\subseteq E}(x-1)^{r(M)-r(A)}(y-1)^{|A|-r(A)}. It is well known that T(M^{*};x,y)=T(M;y,x) for a matroid M and its dual M^{*} . In-depth accounts of the Tutte polynomial and its applications can be found in [ 1 ] and [ 3 ] . In [ 1 , Exercise 6.10(b)] , it is noted that T(M;x,y)=T(N;x,y)-xy+x+y if M is obtained from N by relaxing a circuit-hyperplane. Since relaxation is an example of a rank-preserving weak map, this adds to the plausibility of the main result. Before proving the main result in general, we prove it in the specific case when N is comprised solely of loops and coloops. Observe that if there is a rank-preserving weak map from a matroid M to a matroid N , then every coloop of M is a coloop of N , while every loop of M is a loop of N . The proof of the following lemma uses the sign function \text{sgn}:\mathbb{R}\to\{-1,0,1\} where \text{sgn}(x)=\begin{cases}-1&\text{ if }x<0,\\ 0&\text{ if }x=0,\\ 1&\text{ if }x>0.\\ \end{cases} Lemma 4 . Let x>0 and y>0 . Let M be a matroid with rank k , nullity m , and |E|\geq 2 . Then T(M;x,y)\geq x^{k}y^{m} if and only if x+y\geq xy or M\cong U_{k,k}\oplus U_{0,m} . Moreover, if M\not\cong U_{k,k}\oplus U_{0,m} , then T(M;x,y)>x^{k}y^{m} if and only if x+y>xy . Proof. Suppose M\not\cong U_{k,k}\oplus U_{0,m} . We argue by induction on |E| that \text{sgn}(T(M)-x^{k}y^{m})=\text{sgn}(x+y-xy) , where we have abbreviated T(M;x,y) as T(M) . If |E|=2 , then M\cong U_{1,2} and T(M;x,y)=x+y . Therefore \text{sgn}(T(M)-xy)=\text{sgn}(x+y-xy) , and the result holds. Assume that the result holds for |E|<n and let |E|=n\geq 3 . Since M\not\cong U_{k,k}\oplus U_{0,m} , there is an element e of M that is neither a loop nor a coloop. Thus T(M)=T(M\backslash e)+T(M/e) . Suppose M\backslash e\cong U_{k,k}\oplus U_{0,m-1} . Then M\cong U_{s,s+1}\oplus U_{k-s,k-s}\oplus U_{0,m-1} for some s with 1\leq s\leq k . If s=1 , then M/e\cong U_{k-1,k-1}\oplus U_{0,m} . Thus T(M\backslash e)=x^{k}y^{m-1} and T(M/e)=x^{k-1}y^{m} . Since x>0 and y>0 , \displaystyle\text{sgn}(T(M)-x^{k}y^{m}) \displaystyle=\text{sgn}(x^{k}y^{m-1}+x^{k-1}y^{m}-x^{k}y^{m}) \displaystyle=\text{sgn}(x^{k-1}y^{m-1}(x+y-xy))=\text{sgn}(x+y-xy), as desired. Suppose s\geq 2 . Then M/e\not\cong U_{k-1,k-1}\oplus U_{0,m} and, by the induction assumption, \displaystyle\text{sgn}(T(M/e)-x^{k-1}y^{m}) \displaystyle=\text{sgn}(x+y-xy). Now, by the deletion-contraction formula for T(M) , \displaystyle\text{sgn}(T(M)-x^{k}y^{m}) \displaystyle=\text{sgn}(T(M/e)+x^{k}y^{m-1}-x^{k}y^{m}) \displaystyle=\text{sgn}(T(M/e)-x^{k-1}y^{m-1}(xy-x)). If \text{sgn}(x+y-xy)=1 , then y>xy-x and T(M/e)>x^{k-1}y^{m-1}(y) . Hence \text{sgn}(T(M/e)-x^{k-1}y^{m-1}(xy-x))=1=\text{sgn}(T(M)-x^{k}y^{m}) . Applying analogous arguments

Read the complete text