Transfer-matrix methods meet Ehrhart theory

Alexander Engstrom*, Florian Kohl

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

Abstract

Transfer-matrix methods originated in physics where they were used to count the number of allowed particle states on a structure whose width n is a parameter. Typically, the number of states is exponential in n. One mathematical instance of this methodology is to enumerate the proper vertex colorings of a graph of growing size by a fixed number of colors.

In Ehrhart theory, lattice points in the dilation of a fixed polytope by a factor k are enumerated. By inclusion-exclusion, relevant conditions on how the lattice points interact with hyperplanes are enforced. Typically, the number of points are (quasi-) polynomial in k. The text-book example is that for a fixed graph, the number of proper vertex colorings with k colors is polynomial in k.

This paper investigates the joint enumeration problem with both parameters n and k free. We start off with the classical graph colorings and then explore common situations in combinatorics related to Ehrhart theory. We show how symmetries can be explored to reduce calculations and explain the interactions with Discrete Geometry. (C) 2018 Elsevier Inc. All rights reserved.

Original languageEnglish
Pages (from-to)1-37
Number of pages37
JournalADVANCES IN MATHEMATICS
Volume330
DOIs
Publication statusPublished - 25 May 2018
MoE publication typeA1 Journal article-refereed

Keywords

  • The transfer-matrix method
  • Ehrhart theory
  • Reciprocity
  • Graph coloring
  • The chromatic polynomial
  • Markov chains
  • DIMER PROBLEM
  • POLYNOMIALS
  • POLYTOPES
  • NUMBERS
  • GRAPHS

Cite this