Transfer-matrix methods meet Ehrhart theory (Q1644957)

Let \(G\) be an arbitrary graph and \(P_n\) (\(C_n\)) be the path (cycle) graph on \(n\) nodes, respectively. By examining proper \(k\)-colorings of Cartesian graph products of the form \(G \times P_n\) and \(G \times C_n\), the authors want to answer the following problems: 1. How many proper \(k\)-colorings does the Cartesian graph product \(G\times P_n\) have? 2. Asymptotically, how many proper \(k\)-colorings does the Cartesian graph product \(G \times C_n\) have? The authors introduce proper colorings, acyclic orientations, and the Cartesian graph product. Also, they introduce a transfer-matrix method and show how one can use this to count the number of proper colorings when the number of colors is fixed. Using the method given by \textit{M. Beck} and \textit{T. Zaslavsky} [Adv. Math. 205, No. 1, 134--162 (2006; Zbl 1107.52009)], the authors define inside-out polytopes and show how to count proper colorings of \(G \times P_n\) when \(n\) is fixed. They illustrate how one can use symmetry to define a compactified transfer matrix \(L\), whose size does not depend on \(n\). The authors combine transfer-matrix methods with the Ehrhart theory. They use group actions, restricted \(k\)-colorings and orbits to establish a compactified transfer matrix \(L\), whose size does not depend on \(k\). They then show that the biggest eigenvalue of \(L\) equals the biggest eigenvalue of the transfer matrix \(A_{M_G}\) for all \(k\). By using the matrix \(L\), the authors explicitly compute the chromatic polynomial of \(G \times P_n\). The authors prove that the set of proper \(k\)-colorings stays invariant under a permutation of colors. The authors then show that the graph \(G\) itself also has a symmetry group, called the automorphism group of \(G\). They quotient by the group coming from permuting the colors. Also, the authors quotient out by a possibly trivial subgroup of the automorphism group. The authors deal with finding the explicit number of orbits after quotienting by permutations of colors. They then use a similar approach to obtain new results about counting discrete Markov chains. They show that a similar philosophy can be used to count the number of discrete Markov chains. The result in a general form is formulated.