Abstract
Suppose that the vertices of Z^d are assigned random colors via a finitary factor of independent identically distributed (i.i.d.) vertexlabels. That is, the color of vertex v is determined by a rule that examines the labels within a finite (but random and perhaps unbounded) distance R of v, and the same rule applies at all vertices. We investigate the tail behavior of R if the coloring is required to be proper (i.e., if adjacent vertices must receive different colors). When d≥2, the optimal tail is given by a power law for 3 colors, and a tower (iterated exponential) function for 4 or more colors (and also for 3 or more colors when d=1). If proper coloring is replaced with any shift of finite type in dimension 1, then, apart from trivial cases, tower function behavior also applies.
Original language  English 

Pages (fromto)  28672898 
Number of pages  32 
Journal  Annals of Probability 
Volume  45 
Issue number  5 
Early online date  23 Sep 2017 
DOIs  
Publication status  Published  23 Sep 2017 
Bibliographical note
Proxy date of acceptance added to output record.Fingerprint
Dive into the research topics of 'Finitary Coloring'. Together they form a unique fingerprint.Profiles

Professor Alexander E Holroyd
Person: Academic