The α \alpha -representation for the Tait coloring and for the characteristic polynomial of matroid

Eduard Lerner · 2025

Read The α \alpha -representation for the Tait coloring and for the characteristic polynomial of matroid by Eduard Lerner (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-2503-14285.txt.

Introduction

Eduard Lerner builds a formula style, called the alpha-representation, for counting colorings and for a key matroid polynomial, in a 2025 math paper. The method is borrowed from physics, where it rewrites vacuum Feynman amplitudes. Here the stage is a finite field with odd prime power size, and the objects are regular matroids with their families of bases. A weighted sum over bases anchors the work.

Lerner picks the largest set where that sum stays nonzero and rewrites the matroid's characteristic polynomial at the field size as a mix of Legendre symbols. The result extends his earlier flow polynomial formula for graphs. The same tools express counts of Tait colorings of cubic planar graphs through face matrix minors.

Catalog record

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

Source: https://arxiv.org/abs/2503-14285

Browse the full library · About the Tower of Babel

Full text

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

The α \alpha -representation for the Tait coloring and for the characteristic polynomial of matroid Eduard Lerner Abstract Consider a finite field 𝔽 q \mathbb{F}_{q} , q = p d q=p^{d} , where p p is an odd number. Let M = ( E , r ) M=(E,r) be a regular matroid; denote by ℬ {\mathcal{B}} the family of its bases, s ¯ ​ ( M , α ) = ∑ B ∈ ℬ ∏ e ∉ B α e \bar{s}(M;\alpha)=\sum_{B\in{\mathcal{B}}}\prod_{e\not\in B}\alpha_{e} , where α e ∈ 𝔽 q {\alpha_{e}\in\mathbb{F}_{q}} , α e ≠ 0 \alpha_{e}\neq 0 . Let a subset A ≡ A ⁡ ( α ) A\equiv A(\alpha) in E E have the maximal cardinality and satisfy the condition s ¯ ​ ( M | A ; α ) ≠ 0 \bar{s}(M|A;\alpha)\neq 0 , while r ∗ ​ ( α ) = | A | − r ⁡ ( E ) r^{*}(\alpha)=|A|-r(E) . Let us represent the value of the characteristic polynomial of the matroid M M at the point q q as the linear combination of Legendre symbols with respect to s ¯ ​ ( M | A ; α ) \bar{s}(M|A;\alpha) , whose coefficients are modulo equal to 1 / q r ∗ ​ ( α ) / 2 1/q^{r^{*}(\alpha)/2} . This representation generalizes the formula for a flow polynomial of a graph which was obtained by us earlier. The latter formula is an analog of the so-called α \alpha -representation of vacuum Feynman amplitudes in the case of a finite field, which has inspired the Kontsevich conjecture (1997). The α \alpha -representation technique is also applicable for expressing the number of Tait colorings for a cubic biconnected planar graph in terms of principal minors of the matrix of faces of this graph. [type=editor, auid=000,bioid=1, orcid=0000-0001-5129-5820 ] keywords matroid ,characteristic polynomial,Tait coloring,Legendre symbol,Laplace–Kirchhoff matrix,Gaussian sum , , MSC: ,primary 05B35, 05C31,secondary 11T06 † † titlenote: The research was supported by RSF (project No. 24-21-00158). 1 Introduction 1.1 The historical background and the goal of the paper Since the very appearance of the theory of matroids, its significant problems have been related to finite fields; it suffices to mention the critical problem stated by H. Crapo and G.-C. Rota [ 4 ] . Nevertheless, in calculations of values of characteristic polynomials of matroids, one rarely immediately uses theoretical numerical ingredients. The idea of this paper has a long history. Let the symbol \mathcal{T}(G) stand for the set of spanning trees of the graph G . Consider sums s(G;\alpha)=\sum_{T\in\mathcal{T}(G)}{\prod_{e\in E(T)}{\alpha_{e}}}, (1) where \alpha_{e} are elements of the finite field {\mathbb{F}}_{q} . In December 1997, when giving a talk at the Gelfand seminar at Rutgers University, Maxim Kontsevich proposed a conjecture that the number of nonzero values of ( 1 ) for \alpha\in\mathbb{F}_{q}^{E} is a polynomial with respect to q . This conjecture was inspired by studying analogous sums (with complex-valued \alpha_{e} ) in the quantum field theory. Though the conjecture was never published, it has aroused the interest of experts in combinatorics (see [ 16 , 3 , 17 ] ). This conjecture allows a natural generalization for matroids, while all possible bases of a matroid represent an analog of \mathcal{T}(G) . However, the increased interest to the Kontsevich conjecture and its generalization has negatively affected the development of such techniques, when sometime later this conjecture was refuted [ 2 ] . Nevertheless, accurately adjusting \alpha -representation techniques used in the quantum theory for fields of real values for the case of finite fields 1 1 1 See Remark 4 (subsection 3.1 ) for the brief history of the term “ \alpha -representation”. , we get a new representation for the flow polynomial of the graph [ 6 ] . The goal of this paper is to generalize results obtained in the paper [ 6 ] for the case of arbitrary regular matroids and to apply the \alpha -representation technique for deriving explicit formulas in the case, which plays an important role in the graph theory. Namely, we, in particular, consider the number of Tait colorings for a cubic biconnected planar graph. The fact that the number of Tait colorings for any such graph differs from zero is equivalent to the assertion of the Four Colors Theorem. In obtaining the \alpha -representation for the characteristic polynomial of an arbitrary regular matroid the fact that the representation matrix is unimodular plays an important role. In a non-regular case, we get a more complicated formula which depends on the representation matrix of the matroid over the field \mathbb{F}_{q} . The expression for the number of Tait colorings for a cubic planar graph G has appeared to be rather simple. It is related to the matrix of faces of this graph, which (as far as we know) was not studied earlier. In this matrix, rows and columns correspond to all possible faces F_{i} of the graph G . The i,j -th element of this matrix equals the sum of values of variables \alpha(v) , where v is the vertex, which belongs to both faces F_{i} and F_{j} , while \alpha(v) are nonzero variables in the field \mathbb{F}_{3} associated with the graph vertices (we treat these variables, which take on values \pm 1 , as spins). The number of Tait colorings depends on the sum of Legendre symbols of principal nonzero minors of this matrix with the maximal possible rank with respect to all possible \alpha . The rest part of the paper has the following structure. In the next subsection we state the main results, below we give an illustrative example for them. Section 2 is devoted to auxiliary assertions used in the proof of the main results. In particular, we state (and later prove) a more general theorem, which is valid for all matroids representable over the field \mathbb{F}_{q} . An important role in this research is played by (adduced in subsection 2.5 ) expressions for the characteristic function of the dual matroid in terms of representation matrices of the initial matroid and properties of the generalized Laplace–Kirchhoff matrix of an arbitrary matroid. In subsection 2.6 , we also recall the Heawood theorem for the number of Tait colorings; below we make use of this theorem. In the application of the \alpha -representation in the case of a real field, one uses explicit formulas for calculating Gaussian integrals. In the case of a finite field, in subsection 2.7 we consider multidimensional Gaussian sums. Section 3 is immediately devoted to the \alpha -representation. We first prove the theorem on the number of Tait colorings. Those, who are interested only in understanding this result, may restrict themselves to reading only corresponding parts of subsections 1.2 and 1.3 and, after getting acquainted with subsections 2.6 , 2.7 , read this proof in Section 3 . We use it for clarifying a rather simple principle of the proof of the main result about the alpha-representation of matroids. We believe that after a thorough preparation a reader would easily understand this idea. In Conclusion, we summarize the obtained results and discuss the further development of this work. 1.2 Denotations and statements of main results Let us exactly state the main results of this paper. We

Read the complete text