Tutte polynomial, complete invariant, and theta series

DOI10.1007/S00373-020-02238-WMaRDI QIDQ2051875zbMATH OpenOpenAlexFDO

Authors Misaki Kume, Tsuyoshi Miezaki, Hidehiro Shinohara, Tadashi Sakuma

Publication date 25 November 2021

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2007.15089

zbMATH Keywords

codegraph-invariant polynomiallatticematroidtheta seriesTutte polynomialweight enumerator

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Graph polynomials (05C31) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Linear codes (general theory) (94B05) Applications of the theory of convex sets and geometry of numbers (covering radius, etc.) to coding theory (94B75)

Abstract: In this study, we present two results that relate Tutte polynomials. First, we provide new and complete polynomial invariants for graphs. We note that the number of variables of our polynomials is one. Second, let L_1 and L_2 be two non-isomorphic lattices. We state that L_1 and L_2 are theta series equivalent if those theta series are the same. The problem of identifying theta series equivalent lattices is discussed in Prof.~Conway's book The Sensual (Quadratic) Form with the title "Can You Hear the Shape of a Lattice?" In this study, we present a method to find theta series equivalent lattices using matroids and their Tutte polynomials.

Review text

The authors prove two results unrelated to each other, both inspired by Tutte polynomials. In the first part, they start with an undirected finite graph \(G\) with \(n\) vertices and show that \(G\) can be completely recovered from an \(n\)-state polynomial \(Z_n = Z_{W_n}(G)\) in \(n(n+1)/2\) variables. By this they mean that the number of vertices, edges, and adjacencies can be recovered from the polynomial. As a result, the set \(\{Z_n\}_{n=1}^\infty\) forms a set of complete invariants for finite graphs. They go on to show that \(G\) can also be recovered from the similarly defined pseudo \(n\)-state polynomial \(\tilde{Z_n} = Z_{\tilde{W_n}}(G)\) in one variable of degree \(3|E(G)|\) yielding a similar conclusion about the set \(\{\tilde{Z_n}\}_{n=1}^\infty\). In the second part, they prove that non-isomorphic lattices of rank \(4d\) with the same \(\Theta\)-series exist for \(d \in \{24,27,30,33,35,36,38,39,41,42\} \cup\) \(\{i \in \mathbb{Z} \mid i \geq 44\}\).

Recommendations

• On the Tutte polynomial
• Contraction-deletion invariants for graphs
• scientific article; zbMATH DE number 67324
• On graphs determined by their Tutte polynomials
• A generalization of the Tutte polynomials

Cites work

• A Contribution to the Theory of Chromatic Polynomials
• A generalization of the Tutte polynomials
• A note on Nagami's polynomial invariants for graphs
• Classification of ternary extremal self-dual codes of length 28
• Contraction-deletion invariants for graphs
• Even lattices and doubly even codes
• Graph invariants related to statistical mechanical models: Examples and problems
• scientific article; zbMATH DE number 3534506 (Why is no real title available?)
• scientific article; zbMATH DE number 1224949 (Why is no real title available?)
• scientific article; zbMATH DE number 1092357 (Why is no real title available?)
• scientific article; zbMATH DE number 3049182 (Why is no real title available?)
• Lattices and codes. A course partially based on lectures by Friedrich Hirzebruch
• On dichromatic polynomials
• On isomorphism problems for vertex operator algebras associated with even lattices
• Polynomial Invariants of Graphs
• Polynomial invariants of graphs with state models
• The Magma algebra system. I: The user language
• Type II codes, even unimodular lattices, and invariant rings
• Weight Enumeration and the Geometry of Linear Codes

Cited in

(1)

• Some remarks one the sieve formula, the Tutte polynomial and Crapo's beta invariant

Describes a project that uses

Uses Software

• Magma
• Mathematica

This page was built for publication: Tutte polynomial, complete invariant, and theta series

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2051875)