Lattice point counts for the Shi arrangement and other affinographic hyperplane arrangements》.pdfVIP

Journal of Combinatorial Theory, Series A 114 (2007) 97–109 /locate/jcta Lattice point counts for the Shi arrangement and other affinographic hyperplane arrangements David Forge a,1, Thomas Zaslavsky b a Laboratoire de Recherche en Informatique UMR 8623, Bât. 490, Université Paris-Sud, 91405 Orsay Cedex, France b Department of Mathematical Sciences, State University of New York at Binghamton, Binghamton, NY 13902-6000, USA Received 17 August 2005 Available online 15 June 2006 Abstract Hyperplanes of the form xj = xi + c are called affinographic. For an affinographic hyperplane arrange- ment in Rn , such as the Shi arrangement, we study the function f (m) that counts integral points in [1, m]n that do not lie in any hyperplane of the arrangement. We show that f (m) is a piecewise polynomial function of positive integers m, composed of terms that appear gradually as m increases. Our approach is to convert the problem to one of counting integral proper colorations of a rooted integral gain graph. An application is to interval coloring in which the interval of available colors for vertex vi has the form [hi + 1, m]. A related problem takes colors modulo m; the number of proper modular colorations is a different piece- wise polynomial that for large m becomes the characteristic polynomial of the arrangement (by which means Athanasiadis previously obtained that polynomial). We also study this function for all positive moduli. © 2006 Elsevier Inc. All rights reserved. Keywords: Integral gain graph; Modular gain graph; Proper coloring; Interval graph coloring; Chromatic function; Affinographic hyperplane arrangement; Deformatio