Multivariate Tutte polynomials of semimatroids

2025

Read Multivariate Tutte polynomials of semimatroids (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-2508-00561.txt.

Introduction

Houshan Fu introduces multivariate Tutte polynomials for semimatroids, in a record whose catalog entry lacked author data while the head names the single author. Semimatroids generalize graphs and matroids, and their polynomial invariants generalize the classic ones. Several variants are defined together, including dichromatic, subset corank, size corank, and rank generating polynomials.

Deletion contraction recurrences are established for the new ones. To delete or shrink one part and see how the count shifts is a core move in this work, and the rules for that move are set out in full. Basis activities expansions give a second way to view their build. Various convolution identities connect them. The findings extend two known results to semimatroids: the convolution formula of Kook, Reiner, and Stanton, and the convolution multiplication identities of Kung, both first shown for graphs and matroids. This shared treatment clarifies how these counting polynomials behave under local changes.

Catalog record

YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE39 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-00561

Browse the full library · About the Tower of Babel

Full text

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

Multivariate Tutte polynomials of semimatroids Abstract We introduce and investigate multivariate Tutte polynomials, dichromatic polynomials, subset-corank polynomials, size-corank polynomials, and rank generating polynomials of semimatroids, which generalize the corresponding polynomial invariants of graphs and matroids. We primarily establish their deletion-contraction recurrences, basis activities expansions, and various convolution identities. These findings naturally extend Kook-Reiner-Stanton’s convolution formula and Kung’s convolution-multiplication identities for the Tutte polynomials of graphs and matroids to semimatroids. Keywords: Semimatroid, multivariate Tutte polynomial, deletion-contraction recurrence, basis activities expansion, convolution formula Mathematics Subject Classifications: 05C31, 05B35 Houshan Fu School of Mathematics and Information Science Guangzhou University Guangzhou 510006, Guangdong, P. R. China Email: [email protected] 1 Introduction In this paper, we primarily introduce and investigate multivariate Tutte polynomials, dichromatic polynomials, subset-corank polynomials, size-corank polynomials, and rank generating polynomials of semimatroids, particularly focusing on their alternative descriptions, various convolution formulae, and connections to the standard Tutte polynomial and characteristic polynomial. Characteristic and Tutte polynomials are the most important and extensively studied polynomial invariants in graphs, matroids, hyperplane arrangements, arithmetic matroids, and semimatroids. The Tutte polynomial originates from the chromatic polynomial, a graph polynomial arising in graph coloring [ 15 ] . To address the four colour problem, Birkhoff [ 3 ] introduced the chromatic polynomial for planar graphs in 1912, later generalized to arbitrary graphs by Whitney [ 19 , 20 ] . In 1964, Rota [ 13 ] defined the characteristic polynomial of matroids as an extension of the chromatic polynomial. Subsequently, Crapo [ 5 ] further introduced the Tutte polynomial for matroids in terms of internal and external activities of bases, generalizing the characteristic polynomial and showing that its coefficients are nonnegative integers. This combinatorial definition is now known as Crapo’s formula (also referred to as the basis activities expansion ). Theorem 1.1 ( [ 5 ] , Crapo’s formula) . Let M=(E,r) be a matroid. Then the Tutte polynomial T(M;\lambda,x) of M can be expressed as T(M;\lambda,x)=\sum_{B\text{ is a basis of }M}\lambda^{|{\rm IA}(B)|}x^{|{\rm EA}(B)|}, where {\rm IA}(B) is the set of internally activity elements and {\rm EA}(B) is the set of externally activity elements with respect to a basis B of M . In 2007, Ardila [ 1 ] extended the characteristic and Tutte polynomials to semimatroids. A semimatroid is an abstract structure that captures the dependence properties of affine hyperplane arrangements, generalizing the concept of matroids. This was created by Wachs and Walker [ 17 ] in terms of the “geometric lattice” of closed sets, and later developed a comprehensive theory in terms of subsets of a finite set by Ardila [ 1 ] (also discovered independently by Kawahara [ 8 ] ). Ardila focused on Tutte polynomials for semimatroids, establishing a deletion-contraction formula [ 1 , Proposition 8.2] and extending Crapo’s formula [ 1 , Theorem 9.5] . However, the characteristic polynomials of semimatroids received limited attention until Fu [ 7 ] , who studied their fundamental properties and further provided convolution formulae for both the Tutte polynomial and the multiplicative characteristic polynomial of semimatroids. Our original motivation is to find a general polynomial that encompasses both the Tutte and characteristic polynomials of semimatroids, and to better understand their equivalent characterizations and convolution identities. Recently, Sokal [ 14 ] introduced a multivariate generalization of the Tutte polynomial for graphs and matroids–known to physicists as the Potts-model partition function. The multivariate Tutte polynomial assigns a variable x_{e} for every element e of a matroid, along with an extra variable \lambda . In particular, when all the variables x_{e} are set to the same variable x , it reduces to a bivariate polynomial, known as the dichromatic polynomial, which is essentially equivalent to the standard Tutte polynomial. In 2014, Brändeń and Moci [ 4 ] generalized this multivariate Tutte polynomial to arithmetic matroids, providing a deletion-contraction recurrence and a generalization of Crapo’s formula. Inspired by Sokal’s work, we introduce a multivariate Tutte polynomial for a semimatroid (E,\mathcal{C},r_{\mathcal{C}}) , defined as follows: Z(\mathcal{C};\lambda,\bm{x}):=\sum_{A\in\mathcal{C}}\lambda^{-r_{\mathcal{C}}(A)}\Big[\prod_{e\in A}x_{e}\Big]=\sum_{A\in\mathcal{C}}\lambda^{-r_{\mathcal{C}}(A)}\bm{x}^{A}. which naturally extends the multivariate Tutte polynomial for matroids. For this polynomial, we first present a deletion-contraction formula in Theorem 2.1 and a generalization of Crapo’s formula in Theorem 2.3 . In addition, when all the variables x_{e} are set to the same variable x , this specializes to the following dichromatic polynomial : Z(\mathcal{C};\lambda,x):=\sum_{A\in\mathcal{C}}\lambda^{-r_{\mathcal{C}}(A)}x^{|A|}. As a direct consequence of Theorem 2.1 and Theorem 2.3 , we derive its deletion-contraction recurrence and basis activities expansion in Subsection 2.2 . Furthermore, we also provide convolution formulae for the multivariate Tutte polynomial of semimatroids in Theorem 2.6 , and for the dichromatic polynomial in Subsection 2.3 . This extends independent work by Kook, Reiner and Stanton [ 9 ] , and Etienne and Las Vergnas [ 6 ] , who established a so-called convolution formula for the standard Tutte polynomial of a matroid M=(E,r) : T(M;\lambda,x)=\sum_{T\subseteq E}T(M|T;0,x)T(M/T;\lambda,0). (1.1) In 2004, Kung discovered a convolution formula for multiplicative characteristic polynomials of matroids. Subsequently, Kung [ 11 ] generalized this result to the subset-corank and size-corank polynomials of matroids, both closely related to the multivariate and standard Tutte polynomials, respectively. In 2015, Wang [ 18 ] introduced Möbius conjugation of posets as a unified framework for reproving previous convolution formulae and established the first convolution formula for multiplicative characteristic polynomials of hyperplane arrangements. Most recently, a number of convolution formulae for arithmetic Tutte polynomials were developed by Backman and Lenz [ 2 ] , and for multivariate arithmetic Tutte polynomials were established by Ma, Jin and Yang [ 12 ] . Motivated by Kung’s work [ 11 ] , we further introduce and study the subset-corank, size-corank, and rank generating polynomials for semimatroids in Section 3 . Note that the subset-corank polynomial is essentially equivalent to the multivariate Tutte polynomial under certain parametrizations, while both the size-corank and rank-generating polynomials are equivalent to the dichromatic polynomial. By applying those results for the multivariate Tutte polynomial of semimatroids to the subset-corank polynomial, we can deduce the corresponding deletion-contraction formula, basis activities expansion, and convolution formulae in Section 3 . Similarly, when all the variables x_{e} are specialized to a common variable x , the subset-corank polynomial reduces to the size-corank polynomial. Consequently, the established properties–deletion-contraction formula, basis activities expansion, and convolution formulae–are straightforwardly extended to both the size-corank and rank-generating polynomials, as shown in Section 3 and Section 3 . These findings extend Kung’s results in [ 11 ] to semimatroids. This paper is structured as follows. In Section 2 , we begin by reviewing necessary definitions and results related to semimatroids, followed by the introduction and analysis of their multivariate Tutte polynomials and dichromatic polynomials–with a particular emphasis on their diverse descriptive forms and convolution identities. Building on these findings, we further investigate analogous properties of the subset-corank, size-corank, and rank generating polynomials of semimatroids in Section 3 . 2 Multivariate Tutte polynomial In this section, we first present the multivariate Tutte polynomials and dichromatic polynomials of semimatroids, which extend the corresponding polynomials defined for matroids or graphs. We then investigate their properties pertaining to different descriptive forms and convolution identities. 2.1 Basic definitions We begin with the necessary definitions and results connecting semimatroids, which may be needed later. For further reading on this topic, we refer the reader to

Read the complete text