Transfer-Matrix Methods Meet Ehrhart Theory
joint with Alexander Engström, Aalto University

Florian Kohl
Freie Universität Berlin/Berlin Mathematical School

16th of January,2017

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

1 Motivation
2 Background and Notation
3 Special Cases

The Transfer-Matrix Method
Inside-Out Polytopes
4 Symmetry and the General Case
5 Concluding Remarks

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

Outline1 Motivation
2 Background and Notation
3 Special Cases

The Transfer-Matrix Method
Inside-Out Polytopes
4 Symmetry and the General Case
5 Concluding Remarks

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

Figure: A Cartesian graph product in the wild (Credit: Rutgers
University)

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

Outline1 Motivation
2 Background and Notation
3 Special Cases

The Transfer-Matrix Method
Inside-Out Polytopes
4 Symmetry and the General Case
5 Concluding Remarks

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

A graph G is a pair (V , E ), where V is the set of nodes andwhere E is the set of edges.

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

A graph G is a pair (V , E ), where V is the set of nodes orvertices and where E is the set of edges.
We denote the path graph on n vertices by Pn and the cycle
graph on n vertices by Cn .

Figure: C4 and P3

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

A graph G is a pair (V , E ), where V is the set of nodes orvertices and where E is the set of edges.
We denote the path graph on n vertices by Pn and the cycle
graph on n vertices by Cn .
A proper k-coloring of G is a map c : V −→ {1, 2, . . . , k}such that c(v ) 6= c(u) for all u, v with {u, v } ∈ E .
1

1

2

1

1

2

Figure: A proper 2-coloring and a non-proper 2-coloring
F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

For a simple graph G , we define the counting function
χG (k) := #proper k-colorings of G .

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

For a simple graph G , we define the counting function
χG (k) := #proper k-colorings of G .
χG is a polynomial of degree N = #V (G ) with leading
coefficient 1. χG is called the chromatic polynomial of G .

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

For a simple graph G , we define the counting function
χG (k) := #proper k-colorings of G .
χG is a polynomial of degree N = #V (G ) with leading
coefficient 1.
χG (−1) counts the number of acyclic orientations of G .
This is a special case of a reciprocity theorem for χG .

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

For a simple graph G , we define the counting function
χG (k) := #proper k-colorings of G .
As it turns out, χG is a polynomial of degree N = #V (G )with leading coefficient 1.
χG (−1) counts the number of acyclic orientations of G .
This is a special case of a reciprocity theorem for χG .
We are interested in the number of proper k-colorings of
G × Pn or G × Cn , where k and n are variables.

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

For graphs G1 = (V1 , E1 ) and G2 = (V2 , E2 ) the Cartesian
product G1 × G2 is the graph with vertex set V1 × V2
The vertices (u1 , v1 ) and (u2 , v2 ) are connected by an edge if(u1 = u2 and {v1 , v2 } ∈ E2 ) or if (v1 = v2 and {u1 , u2 } ∈ E1 ).

Figure: C4 × P3 and P3 × P6 .
F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

Question
Let G be any graph and let n and k be positive integers. How
many proper k-colorings of G × Pn are there?

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

Question
Let G be any graph and let n and k be positive integers. How
many proper k-colorings of G × Pn are there?
Question
What is the asymptotic behavior of the number of proper
k-colorings of G × Cn as k, n → ∞?

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

Outline1 Motivation
2 Background and Notation
3 Special Cases

The Transfer-Matrix Method
Inside-Out Polytopes
4 Symmetry and the General Case
5 Concluding Remarks

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

There are two special cases:
k is fixed and n is not =⇒ Transfer-Matrix Method, see e. g.
[8].
n is fixed and k is not =⇒ Inside-Out Polytopes, see [1].

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

The Transfer-Matrix Method

The Transfer-Matrix Method:
The transfer-matrix method is classically used to count walkson (weighted di-)graphs.

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

The Transfer-Matrix Method

The Transfer-Matrix Method:
The transfer-matrix method is classically used to count walkson (weighted di-)graphs.
Let (Ai,j )i,j be the adjacency matrix of a graph (V , E ), i. e.,Ai,j = 1 if {vi , vj } ∈ E and 0 otherwise.

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

The Transfer-Matrix Method

The Transfer-Matrix Method:
The transfer-matrix method is classically used to count walkson (weighted di-)graphs.
Let (Ai,j )i,j be the adjacency matrix of a graph (V , E ), i. e.,Ai,j = 1 if {vi , vj } ∈ E and 0 otherwise.
ExampleIf G = C3 , then



0 1 1
A = 1 0 1 
1 1 0

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

The Transfer-Matrix Method

The Transfer-Matrix Method:
The transfer-matrix method is classically used to count walkson (weighted di-)graphs.
Let (Ai,j )i,j be the adjacency matrix of a graph (V , E ), i. e.,Ai,j = 1 if {vi , vj } ∈ E and 0 otherwise.
Transfer-Matrix Theorem
For a nonnegative integer n, (An )i,j counts the number of walks oflength n from vi to vj .

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

The Transfer-Matrix Method

The Transfer-Matrix Method:
Transfer-Matrix Theorem
For a nonnegative integer n, (An )i,j counts the number of walks oflength n from vi to vj .
Example continued
If G = C3 , then



0 1 1
A = 1 0 1 
1 1 0
and

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory




2 1 1
A2 = 1 2 1 .
1 1 2
FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

The Transfer-Matrix Method

We want to count the number of proper k-colorings of G × Pn
for fixed k. To use the transfer-matrix method, we establish aconnection between walks of length n and colorings of G × Pn .

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

The Transfer-Matrix Method

We want to count the number of proper k-colorings of G × Pn
for fixed k. To use the transfer-matrix method, we establish aconnection between walks of length n and colorings of G × Pn .
We associate a new graph MG to G .

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

The Transfer-Matrix Method

We want to count the number of proper k-colorings of G × Pn
for fixed k.
We now associate a new graph MG to G .
The vertices of MG are labeled by the proper k-colorings of G .
Two vertices are connected by an edge if they form a propercoloring of G × P2 .
ExampleLet k be 3 and let G = P3 . Then MG looks like:

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

The Transfer-Matrix Method(2,3,2)(1,2,1)(3,1,3)(1,3,1)(3,2,3)(2,1,2)(2,1,3)(3,2,1)(1,3,2)(3,1,2)(1,2,3)

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory(2,3,1)

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

The Transfer-Matrix Method

Proper k-colorings of G × Pn+1 are now in bijection withwalks of length n in MG .

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

The Transfer-Matrix Method

Proper k-colorings of G × Pn+1 are now in bijection withwalks of length n in MG .
We can use the adjacency matrix of MG to count exactly
these walks!

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

The Transfer-Matrix Method

Proper k-colorings of G × Pn+1 are now in bijection withwalks of length n in MG .
We can use the adjacency matrix AMG of MG to count exactly
these walks!
Similarly, the number of closed walks (= the number ofcolorings of G × Cn+1 ) is counted by the trace of AnMG .

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

The Transfer-Matrix Method

Proper k-colorings of G × Pn+1 are now in bijection withwalks of length n in MG .
We can use the adjacency matrix AMG of MG to count exactly
these walks!
Similarly, the number of closed walks (= the number ofcolorings of G × Cn+1 ) is counted by the trace of AnMG
Asymptotically, the trace is dominated by λn−1
max , where λmax isthe biggest eigenvalue, which is real and positive by the
Frobenius-Perron theorem.

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

The Transfer-Matrix Method

Figure: The adjacency matrix for MP3 for 4 colors
F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

The Transfer-Matrix Method

Conclusions
The size of the matrix depends on k =⇒ we can’t directly use
this technique for k not fixed.
The size of the matrix is big, so even for fixed k this iscomputationally challenging.
We will use symmetry to obtain a new matrix whose size does
not depend on k and whose biggest eigenvalue is λmax .

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

Inside-Out Polytopes

Inside-Out Polytopes:
If n is fixed and k is a variable, the number of proper coloringsof G × Pn is counted by the chromatic polynomial χ(k).

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

Inside-Out Polytopes

Inside-Out Polytopes:
If n is fixed and k is a variable, then the number of propercolorings of G × Pn is counted by the chromatic polynomial
χ(k).
This has a beautiful interpretation in terms of Ehrhart theory
and inside-out polytopes.

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

Inside-Out Polytopes

Inside-Out Polytopes:
If n is fixed and k is a variable, then the number of propercolorings of G × Pn is counted by the chromatic polynomial.
This has a beautiful interpretation in terms of Ehrhart theory
and inside-out polytopes, see [1].
ExampleLet G = P2 . Then the k-colorings are given by{(x, y ) : x, y ∈ [k] and x 6= y }.

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

Inside-Out Polytopesyy(0, k + 1)
(k, 1)

bijection(1, k)(0, 0)x(k + 1, 0)x

Figure: Integer points inside dashed triangles correspond to proper
k-colorings of P2 .

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

Inside-Out Polytopes

This works in general!
If G is a graph with vertex set V = {x1 , . . . , xn }, then we getan inside-out polytope by taking[
PG := [0, 1]n \Hi,j ,
where we get a forbidden hyperplane Hi,j if {xi , xj } ∈ E . We
also denote this by (P, H), where H is a collection of thehyperplanes.

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

Inside-Out Polytopes

If G is a graph with vertex set V = {x1 , . . . , xn }, then we getan inside-out polytope by taking[
PG := [0, 1]n \Hi,j ,
where we get a forbidden hyperplane Hi,j if {xi , xj } ∈ E .
Counting proper colorings ↔ counting integer points.
=⇒ Enter Ehrhart theory.

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

Inside-Out Polytopes

If P is a lattice polytope, one can define the counting functionEP (t) := # tP ∩ Zd ,which is called the Ehrhart function of P.

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

Inside-Out Polytopes

If P is a lattice d-polytope, one can define the counting
function
EP (t) := # tP ∩ Zd ,which is called the Ehrhart polynomial of P.
Ehrhart famously proved that this is a polynomial of degree dwith leading coefficient vol(P) , see [3].

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

Inside-Out Polytopes

Theorem
Let P be a d-dimensional rational polytope. Then
EP (−t) = (−1)d EP ◦ (t)(1)

where EP ◦ (t) counts the number of integer points in the interior oftP.

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

Inside-Out Polytopes

ExampleLet P = [0, 1]2 . Then EP (t) = (t + 1)2 , and E (2) = 9 andE (−2) = (−1)2 · 1.
(2, 2)(0, 0)
Figure: 2P = [0, 2]2 .

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

Inside-Out Polytopes

Beck and Zaslavsky apply reciprocity to every piece and they
thus get [1, Theorem 4.1]:
Theorem
Reciprocity works for inside-out polytopes, but you need toaccount for multiplicities of the integer points on the hyperplanes.
y(0, k + 1)
(k, 1)(1, k)(0, 0)
F. Kohlx(k + 1, 0)

Figure: Integer points in dashed triangles correspond to proper

Transfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

Inside-Out Polytopes

The reason why the previous results are interesting for us is[1, Theorem 5.1]:
Theorem
For a graph G and the inside-out polytope PG , we have
EPG◦ (t) = χG (t − 1).

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory(2)

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

Inside-Out Polytopes

Theorem
For a graph G and the inside-out polytope PG , we have
EPG◦ (t) = χG (t − 1).

(3)This theorem together with the reciprocity result gives us ageometric proof of Stanley’s recipocity theorem!

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

Inside-Out Polytopes

Theorem
For a graph G and the inside-out polytope PG , we have
EPG◦ (t) = χG (t − 1).

(4)This theorem together with the reciprocity result gives us ageometric proof of Stanley’s recipocity theorem!
Now let’s combine this geometric setup with thetransfer-matrix method!

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

Outline1 Motivation
2 Background and Notation
3 Special Cases

The Transfer-Matrix Method
Inside-Out Polytopes
4 Symmetry and the General Case
5 Concluding Remarks

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

Example revisited
Let G = P3 . We want to count the number of proper k-coloringsof G × Pn , where n and k are variables.

Figure: The adjacency matrix for MP3 for 4 colors
F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

Example revisited
Let G = P3 . We want to count the number of proper k-coloringsof G × Pn , where n and k are variables.
There are essentially two cases:
v1 and v3 have the same color (orbit 1)
v1 and v3 have different colors (orbit 2)
So let’s define a matrix that encodes exactly this information. Thismatrix will be a 2 × 2 matrix.

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

Let A ∈ R 2×2 , where
a1,1 counts the number of proper k-colorings of G × P2 ,where the first copy of G is colored by a representative oforbit 1 and the second has to be in orbit 1.
1
2
1

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

Let A ∈ R 2×2 , where
a1,2 counts the number of proper k-colorings of G × P2 ,where the first copy of G is colored by a representative oforbit 1 and the second has to be in orbit 2.
1
2
1

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

Let A ∈ R 2×2 , wherea2,1 counts the number of proper k-colorings of G × P2 ,where the first copy of G is colored by a representative oforbit 2 and the second has to be in orbit 1.
1
2
3

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

Let A ∈ R 2×2 , where
a2,2 counts the number of proper k-colorings of G × P2 ,where the first copy of G is colored by a representative oforbit 2 and the second has to be in orbit 2.
1
2
3

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

This gives us that 2
k − 3k + 3 k 3 − 6k 2 + 13k − 10A=
k 2 − 4k + 5 k 3 − 6k 2 + 14k − 13for k ≥ 3.
For k = 4, this simplifies to


7 10
A=
.
5 11

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

For a general graph, there are two types of symmetries:
1

relabeling of the colors

2graph automorphisms of G

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

ExampleLet G = P4 . Using a relabeling of colors we get 5 cases.
1

1

3

1

1

2

2

1

2

2

3

1

2

3

1

4

3

1

1

2

Figure: Representatives of the 5 orbits.

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

ExampleLet G = P4 . Then only using a relabeling of colors gives us 5
cases. Also using graph symmetry gives us 4 orbits instead.
1

1

1

1

2

2

2

2

3

1

3

1

4

3

1

2

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

There are two types of symmetries:
1

relabeling of the colors

2graph automorphisms of G

Using these types of symmetry, we can define such a”compactified” matrix A for any graph. A also has the same
biggest eigenvalue as the original adjacency matrix.

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

There are two types of symmetries:
1

relabeling of the colors

2graph automorphisms of G

Using these types of symmetry, we can define such a”compactified” matrix A for any graph. A also has the same
biggest eigenvalue as the original adjacency matrix.
Theorem
The (i, j)-entry of An counts the number of colorings of G × Pn+1 ,where the first G is fixed by a representative of orbit oi and thelast G is colored by an element of orbit oj .

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

Example continued
Let G = P3 . Recall that 2
k − 3k + 3 k 3 − 6k 2 + 13k − 10A=.
k 2 − 4k + 5 k 3 − 6k 2 + 14k − 13Then (A2 )1,1 = k 5 − 9k 4 + 36k 3 − 77k 2 + 87k − 41 counts thenumber of colorings of
1
2
1

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

Example continued
Let G = P3 . Recall that 2
k − 3k + 3 k 3 − 6k 2 + 13k − 10A=.
k 2 − 4k + 5 k 3 − 6k 2 + 14k − 13Then (A5 )1,1 counts the number of colorings of
1
2
1

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

Corollary
Let G × Pn+1 and A be as above. ThenχG ×Pn+1 (k) = (w1 (k), . . . , wp (k))An 1,(5)

where we set wi (k) is the size of orbit i and 1 := (1, . . . , 1)t .
This means that A contains all the information needed to get thechromatic polynomial for every n.

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

Example continued
The chromatic polynomial of P3 × P3 isχ(k) = (w1 , w2 )k 2 − 3k + 3 k 3 − 6k 2 + 13k − 10
k 2 − 4k + 5 k 3 − 6k 2 + 14k − 13

3−1  
1,
1

where w1 = k(k − 1) and w2 = k(k − 1)(k − 2).

Figure: P3 × P3

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

Example continued
The chromatic polynomial of P3 × P4 isχ(k) = (w1 , w2 )k 2 − 3k + 3 k 3 − 6k 2 + 13k − 10
k 2 − 4k + 5 k 3 − 6k 2 + 14k − 13

4−1  
1,
1

where w1 = k(k − 1) and w2 = k(k − 1)(k − 2).

Figure: P3 × P4

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

Example continued
The chromatic polynomial of P3 × P5 isχ(k) = (w1 , w2 )k 2 − 3k + 3 k 3 − 6k 2 + 13k − 10
k 2 − 4k + 5 k 3 − 6k 2 + 14k − 13

5−1  
1,
1

where w1 = k(k − 1) and w2 = k(k − 1)(k − 2).

Figure: P3 × P5

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

Example continued
The chromatic polynomial of P3 × P6 isχ(k) = (w1 , w2 )k 2 − 3k + 3 k 3 − 6k 2 + 13k − 10
k 2 − 4k + 5 k 3 − 6k 2 + 14k − 13

6−1  
1,
1

where w1 = k(k − 1) and w2 = k(k − 1)(k − 2).

Figure: P3 × P6

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

Proposition
Let λmax be the biggest eigenvalue of A (and thus of the adjacency
matrix AMG ). Then
δ(A) ≤ λmax ≤ ∆(A),(6)

where δ(A) and ∆(A) are polynomials of degree N and their twohighest coefficients agree. We also have a combinatorialinterpretation for these coefficients.

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

Example continued
Let G = P3 . The biggest eigenvalue λmax of A satisfies theinequalities
k 3 − 5k 2 + 10k − 8 ≤ λmax ≤ k 3 − 5k 2 + 10k − 7.
The asymptotic behavior of the proper k-colorings of P3 × Cn+1 isdominated by λnmax .

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

Theorem
The row sums of An satisfy a restricted reciprocity theorem fork ≥ N.

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

1

1

2

1

1

3

1

1

2

2

2

1

1

2

1

1

3

1

2

3

3

8

4

8

1

2

1

4

1

4

2

2

1

2

1

8

3

8

3

1

2

3

1

1

2

2

3

3

2

2

2

2

3

1

3

1

2

2

1

2

8

3

2

2

2

3

1

1

1

2

2

1

4

1

1

2

1

3

3

1

3

3

2

2

3

2

3

1

3

3

2

3

2

3

2

2

1

2

3

F. Kohl

8

3

2

2

4

3

4

3

8

2

3

FU Berlin/BMS

Figure: All (1, 2, 3)-restricted, compatible pairs of acyclic orientations

Transfer-Matrix Methods Meet Ehrhart Theory8Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

Outline1 Motivation
2 Background and Notation
3 Special Cases

The Transfer-Matrix Method
Inside-Out Polytopes
4 Symmetry and the General Case
5 Concluding Remarks

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

If we do not use graph automorphisms, we can count the
number of orbits with a deletion-contraction process. This led
to several (new?) recursions for Bell numbers.

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

If we do not use graph automorphisms, we can count the
number of orbits with a deletion-contraction process.
Geometrically, the orbit-decomposition corresponds to afurther subdivision of the inside-out polytope.

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

If we do not use graph automorphisms, we can count the
number of orbits with a deletion-contraction process.
Geometrically, the orbit-decomposition corresponds to afurther subdivision of the inside-out polytopes.
The same philosophy can be applied to many more objects,
e.g., Discrete Markov Processes, and what we call Stacked
Posets.

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

If we do not use graph automorphisms, we can count the
number of orbits with a deletion-contraction process.
Geometrically, the orbit-decomposition corresponds to afurther subdivision of the inside-out polytopes.
The same philosophy can be applied to many more objects,
e.g., Discrete Markov Processes, and what we call Stacked
Posets.
The underlying geometry of inside-out polytopes is behind allof the theorems and proofs.

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

Thanks for your attention!

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

Matthias Beck and Thomas Zaslavsky, Inside-out polytopes.
Adv. Math. 205 (2006), no. 1,p. 134–162.
Ciucu, Mihai, An improved upper bound for the 3-dimensional
dimer problem, Duke Mathematical Journal, Vol 94, Number
1, p. 1–11, 1998
Ehrhart, Eugène, Sur les polyèdres rationnels homothétiques àn dimensions, C. R. Acad. Sci. Paris, Vol. 254, p. 616–618,
1962
Hibi, Takayuki and Higashitani, Akihiro, Smooth Fano
polytopes arising from finite partially ordered sets, Discrete &Computational Geometry. An International Journal of
Mathematics and Computer Science, Vol 45.,Number 3, p.
449–461, 2011
F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

Macdonald, I. G., Polynomials associated with finite
cell-complexes, J. London Math. Soc. (2), Vol. 4, 181–192,
1971
Ohsugi, Hidefumi and Hibi, Takayuki, Convex polytopes all of
whose reverse lexicographic initial ideals are squarefree,
Proceedings of the American Mathematical Society, Vol. 129,
Number 9, p. 2541–2546 (electronic), 2001
Richard Stanley, Acyclic Orientations of Graphs Discrete
Mathematics, Volume 5.,p. 171–178, 1973.
Stanley, Richard, Enumerative combinatorics. Volume 1.
Second edition. Cambridge Studies in Advanced Mathematics,
49. Cambridge University Press, Cambridge, 2012. xiv+626 pp.

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS

Motivation

Background and Notation

Special Cases

Symmetry and the General Case

Concluding Remarks

Richard Stanley, Two poset polytopes, Discrete &Computational Geometry. An International Journal of
Mathematics and Computer Science, Vol. 1, Number 1, p.
9–23, 1986
Winston Yang, Bell numbers and k-trees. Discrete Math. 156(1996), no. 1–3, 247–252.
Ziegler, Günter M., Lectures on polytopes, Graduate Texts in
Mathematics,Vol. 152, Springer-Verlag, New York, 1995

F. KohlTransfer-Matrix Methods Meet Ehrhart Theory

FU Berlin/BMS