Interlace polynomials: enumeration, unimodality and connections to codes

DOI10.1016/J.DAM.2009.11.011MaRDI QIDQ968188zbMATHOpenAlexWikidataFDO

Authors Lars Eirik Danielsen, Matthew G. Parker

Publication date 5 May 2010

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

unimodalityquantum codeslocal complementationcircle graphsinterlace polynomialsquantum graph states

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45)

Abstract: The interlace polynomial q was introduced by Arratia, Bollobas, and Sorkin. It encodes many properties of the orbit of a graph under edge local complementation (ELC). The interlace polynomial Q, introduced by Aigner and van der Holst, similarly contains information about the orbit of a graph under local complementation (LC). We have previously classified LC and ELC orbits, and now give an enumeration of the corresponding interlace polynomials of all graphs of order up to 12. An enumeration of all circle graphs of order up to 12 is also given. We show that there exist graphs of all orders greater than 9 with interlace polynomials q whose coefficient sequences are non-unimodal, thereby disproving a conjecture by Arratia et al. We have verified that for graphs of order up to 12, all polynomials Q have unimodal coefficients. It has been shown that LC and ELC orbits of graphs correspond to equivalence classes of certain error-correcting codes and quantum states. We show that the properties of these codes and quantum states are related to properties of the associated interlace polynomials.

Recommendations

• Interlace polynomials
• The interlace polynomial and the Tutte–Martin polynomial
• The interlace polynomial of a graph
• Coding and Cryptography
• Interlace polynomials of ladder graphs

Cites work

• scientific article; zbMATH DE number 4202305 (Why is no real title available?)
• scientific article; zbMATH DE number 758277 (Why is no real title available?)
• Aperiodic propagation criteria for Boolean functions
• Circle graph obstructions
• Coding and Cryptography
• Edge local complementation and equivalence of binary linear codes
• Euler circuits and DNA sequencing by hybridization
• Generalized Bent Criteria for Boolean Functions (I)
• Graph-based classification of self-dual additive codes over finite fields
• Graphic presentations of isotropic systems
• Interlace polynomials
• Local complementation and interlacement graphs
• Multiparty entanglement in graph states
• On additive GF(4) codes
• On the classification of all self-dual additive codes over \(\text{GF}(4)\) of length up to 12
• Quantum error correction via codes over GF(4)
• Recognition of Circle Graphs
• Some new results for additive self-dual codes over \(\mathrm{GF}(4)\)
• Spectral Orbits and Peak-to-Average Power Ratio of Boolean Functions with Respect to the {I,H,N} n Transform
• The coefficients of the Tutte polynomial are not unimodal
• The interlace polynomial of a graph
• The interlace polynomial of graphs at \(-1\)
• Univariate and Multivariate Merit Factors

Cited in

(4)

• Fast evaluation of interlace polynomials on graphs of bounded treewidth
• Signed permutohedra, delta‐matroids, and beyond
• On graphs and codes preserved by edge local complementation
• Coding and Cryptography

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Interlace polynomials: enumeration, unimodality and connections to codes

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