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 -