Graph Tower Dichromatic Polynomial

Olivier Ramare

Description

Niveau: Supérieur, Licence, Bac+3
Graph Tower Dichromatic Polynomial Olivier Ramare UMR CNRS 8524 Universite de Lille I F-59655 - Villeneuve d'Ascq - France Daniel Tanre UMR CNRS 8524 Universite de Lille I F-59655 - Villeneuve d'Ascq - France March 25, 2008 Abstract Starting from a non-oriented graph G and an integer s, we define the graph tower G(s). In the linear graph G = Lr case, this results in the classical square on r ? s vertices. The aim of this paper is to describe an effective method to compute this dichromatic polyno- mial ZG(s)(q, v) and to prove rationality of the series ?G(q, v)[X] =∑ s≥1 ZG(s)(q, v)X s?1. The functionals created for this purpose are implemented using MuPAD and may be obtained under GPL licence. 1 Dichromatic Polynomial. Let us begin with the definition of the dichromatic polynomial as can be found in [3, Chapter X] or [2]. Connection-contraction principle: The dichromatic polynomial of a (non ori- ented) graph G = (V,E) is a two variables polynomial, denoted by Z(G) or ZG(q, v) if we need this specification.

• oriented graph


• statistical mechanics


• tower


• graph towers


• xa


• edges between


• output variable


• dichromatic polynomial

Sujets

• Directed graph
• Statistical mechanics
• Tutte polynomial

Informations

• Publié par: ondey
• Nombre de lectures: 38
• Langue: English

Extrait

Graph Tower Dichromatic Polynomial
Olivier Ramare Daniel Tanre
UMR CNRS 8524 UMR CNRS 8524
Universite de Lille I Universite de Lille I
F-59655 - Villeneuve d’Ascq - France F-59655 - Villeneuve d’Ascq - France
[e-mail] [e-mail]
March 25, 2008
Abstract
Starting from a non-oriented graph G and an integer s, we de ne
the graph tower G(s). In the linear graph G = L case, this resultsr
in the classical square on rs vertices. The aim of this paper is
to describe an e ective method to compute this dichromatic polyno-
mial Z (q;v) and to prove rationality of the series (q;v)[X] =G(s) GP
s 1Z (q;v)X . The functionals created for this purpose areG(s)s1
implemented using MuPAD and may be obtained under GPL licence.
1 Dichromatic Polynomial.
Let us begin with the de nition of the dichromatic polynomial as can be
found in [3, Chapter X] or [2].
Connection-contraction principle: The dichromatic polynomial of a (non ori-
ented) graph G = (V;E) is a two variables polynomial, denoted by Z(G) or
Z (q;v) if we need this speci cation. It is entirely characterised byG
(
Z(G) =Z(G e) +vZ(G=e);
(1)
rZ(E ) =q ;r
where
{ e is any edge of G
1{ G e is the graph obtained from G by canceling e,
{ G=e is the obtained from G by e and by gluing
together the two ends ofe. This construction is calledconnection-contraction
of the edge e.
{ E is the graph on r vertices without edges.r
Directly from de nition, we get
jVjZ (q; 0) =q ;G
wherejVj denotes the number of vertices of G. The classical chromatic
polynomial is obtained by specializingv = 1 in the dichromatic polynomial.
Determining Z(G) can be done by proceeding edge after edge, following
the above de nition. One can also write Z(G) as the sum over all possible
states where a state is the choice for each edge between cancelation and
connection-contraction. In this latter case, we say we are proceeding by
\clusters".
Partition function: The dichromatic polynomial can be interpreted in Statis-
tical Mechanics as the partition function P of a Potts model with q statesG
on G, through the relation
jEjP (q;) =e Z (q;v); (2)G G
wherejEj denotes the number of edges of G and v = e 1. We do not
give more details here, refering the reader to [3, Section X.3]. Within the
framework of Statistical Mechanics, one of the most important open problem
is the solvability of the partition function for particular graphs like the graph
on the in nite regular lattice of dimension 2. The graph towers we introduce
below were motivated by this problem, quoted by V.F.R. Jones in [4]. We
also may observe that case q = 2, called Ising model, has been solved by L.
Onsager [5]. An explicit presentation of Potts models on di erent lattices
can be found in [1].
Tutte Polynomial: The Tutte polynomial T (x;y) of a graph G is related toG
its dichromatic polynomial by the formula:
m j VjT (x;y) = (x 1) (y 1) Z ((x 1)(y 1); (y 1)) (3)G G
wherem is the number of connected components ofG andjVj the number of
its vertices, cf. [3, Section X.2]. Tutte and dichromatic polynomial contain
many informations on the nature of the graph G, cf. [3, Section X.4].
2Graph Towers: Let s be an integer and G = (E;V ) be a non-oriented graph
withr vertices. Denote byx ;:::;x the vertices ofG. We considers copies1 r
of G built on the vertices x ;:::;x (j = 1;:::;s) such that the number1;j r;j
of edges betweenx andx is exactly the number of edges betweenx anda;j b;j a
x in G. We add one edge between x and x for j = 1;:::;s 1. Theb a;j a;j+1
graph we obtain by this process is called a graph tower and denoted byG(s).
For instance, we have G(1) =G, up to the name of its vertices.
The edges of the copies of G (between x and x ) are called verticala;j b;j
while the edges between x and x are called horizontal.a;j a;j+1
In this paper we describe an e ective method to compute the dichromatic
polynomial of G(s). We also prove that the series
X
s 1 (q;v)[X] = Z (q;v)X (4)G G(s)
s1
is rational in q and v and we compute it.
Denote by L the \linear graph on r vertices", meaning the graph withr
f1;:::;rg as set of vertices and having one and only one edge betweena and
a + 1 if a2f1;:::;r 1g. The graph tower L (s) is the squaring H withr r;s
r lines and s columns built on rs points. The dichromatic polynomial
Z(H ) is the main motivation of this work.r;s
Generalised graph tower: We could have chosen for this study a more general
framework which we describe here. Let s be an integer, G = (E;V ) a non-
oriented graph onr vertices and a bipartite graph, on two sets of r elements.
sWe de ne G
as follows:
{ we consider s copies of G (the \columns" whose edges are \vertical"),
{ we link these columns with the graph adding \horizontal edges" by
this process.
sThe graph tower G(s) is the particular case G
with
= f(i;i); 1irg: (5)
In the rest of this paper we restrict our attention to this case.
2 Presentation of the library.
The script of this library may be obtained (under a GPL licence) at
http://www-gat.univ-lille1.fr/~ramare/ServeurPerso/
3under the names Dichromate.mu et Dichromate.help.
An elementary example: In our program, a graph is a list whose rst element
is the set of vertices and the second one the list of edges. Each edge is the
list of its two adjacent vertices. For instance
G := [f1; 2; 3g; [[1; 1]; [1; 2]; [2; 3]; [3; 1]]] (6)
is the complete graph on three vertices with a loop around vertex 1:
1
2???????
3
Functionals and variables : The vertices are expressions whose equality is
checked with \=". We rst have a functional Dichromate :: DiChromatic( G)
which uses the connection-contraction principle. For the previous example,
we get:
3 2 2 3 3 4 2 2Dichromate :: DiChromatic(G) =q + 3qv + 3q v + 4qv +q v +qv + 3q v :
Since variablesq andv could be reserved for another use, we use DiChromateq
and DiChromatev internally and substitute q and v only for the output.
As for the usual chromatic polynomial, if we wish MuPAD to work with
one variable polynomials, we are simply to specify:
DiChromatev := 1: (7)
Such an explicit speci cation can also be done for the variable DiChromateq.
Output variables q and v are de ned in DiChromateqvxyDefault whose de-
fault value is
DiChromateqvxyDefault := [hold(q); hold(v); hold(x); hold(y)]: (8)
Variables x and y are DiChromatex and DiChromatey internally and are
treated like q and v. They appear in the Tutte polynomial.
4Dichromatic polynomial of a graph tower: Let G be the following graph
1 2
encoded by G := [f1; 2g; [[1; 1]; [1; 2]]]. The polynomial Z (q;v) can beG(2)
determined using
Dichromate :: RectDiChromatic([f1; 2g; [[1; 1]; [1; 2]]]; 2) (9)
which gives
4 4 5 6 7 8 9 2 3 3 2 2 424qv +q v + 68qv + 71qv + 35qv + 9qv +qv + 21q v + 8q v + 51q v
3 3 4 2 2 5 3 4 4 3 2 6 3 5 2 7+ 18q v + 2q v + 40q v + 12q v +q v + 11q v + 2q v +q v (10)
The series (q;v)[X] (cf. 4) can be computed byG
Dichromate :: RectDiChromatic([f1; 2g; [[1; 1]; [1; 2]]]; hold(All)) (11)
which gives
2 2 2 3qv(1 +v) +q (1 +v) Xq v (1 +v)
(12)
2 2 2 2 3 2 21 X(1 +v)(v (4 +v) + 3qv +q ) +X v (1 +v) (v + 2qv +q )
We can specialise q and/or v for this computation but not X which stays
hold(X) all along the evaluation.
Moreover since the linear graph on r vertices L is of special interestr
to us, we can denote it by r in Dichromate :: RectDiChromatic (but not in
Dichromate :: DiChromatic) in such a way that
Dichromate :: RectDiChromatic(2; 3)
(13)
= Dichromate :: RectDiChromatic([f1; 2g; [[1; 2]]]; 3):
This function owns a third optional argument whose special value is TRUE.
Indeed, we have two ways to compute
Dichromate :: RectDiChromatic(r;s):
We can iterate s times the functional described below, or we canG
compute the corresponding power series and take its s-coe cient. As it is,
52Dichromate :: RectDiChromatic(r;s) chooses the rst procedure if sr and
the second one otherwise. Still, the user can prefer iteration, in which case
he should use Dichromate :: RectDiChromatic(r;s; TRUE). This is because
if the computation ofZ (q;v) is clearly faster using the series, the caseL (1000)4
Z (q;v) is unclear. Observe thatL (15)4
Dichromate :: RectDiChromatic(G; 1) = Dichromate :: DiChromatic(G)
though the two procedures are distinct: Dichromate :: DiChromatic uses the
connection-contraction principle, while Dic :: RectDiChromatic works
with cluster expansion in case s = 1.
The Tutte polynomial can be obtained by Dichromate :: RectTutte with
the same parameters than Dichromate :: RectDiChromatic.
By calling
Dichromate :: RectDiChromatic(G; hold(All))
with G = [f1; 2; 3g; [[1; 1]; [1; 2]; [2; 3]; [3; 1]]] already considered in (6), the
reader will discover how intricate our results can be.
3 Graph tower dichromatic polynomial: the
problematic.
Lets be an integer andG = (E;V ) a non-oriented graph onr vertices. Recall
that we are interested in computing Z(G(s)) where G(s) is the graph tower
built on G.
We describe now an algorithm working column by column starting from
the right hand. There are three steps: an initialisation process, a repetitive
step (iteration of the operator ) and a way-out. This algorithm usesG
partitions on the set V of ve