Preprint No. A-02-07

Martin Aigner, Hein van den Holst

Interlace Polynomials

Abstract: In a recent paper Arratia, Bollobas and Sorkin discuss a graph polynomial defined recursively, which they call the interlace polynomial $q(G,x)$. They present several interesting results with applications to the Alexander polynomial and state the conjecture that $|q(G,-1)|$ is always a power of 2. In this paper we use a matrix approach to study $q(G,x)$. We derive evaluations of $q(G,x)$ for various $x$, which are difficult to obtain (if at all) by the defining recursion. Among other results we prove the conjecture for $x=-1$. A related interlace polynomial $Q(G,x)$ is introduced. Finally, we show how these polynomials arise as the Martin polynomials of a certain isotropic system as introduced by Bouchet.

Keywords: Interlace Polynomial, Tutte Polynomial, Binary Matroids, Isotropic Systems

Mathematics Subject Classification (MSC00): 05C50, 05B35

Language: ENG

Available: Pr-A-02-07.ps, Pr-A-02-07.ps.gz

Contact: Martin Aigner, Freie Universität Berlin, Fachbereich Mathematik und Informatik, Arnimallee 2-6, D-14195 Berlin, Germany (aigner@math.fu-berlin.de)

[Home Page] - [Up] - [Search] - [Help] - Created: 20020915 -