First Passage Percolation for Random Colorings of Zᵈ

Random colorings (independent or dependent) of Zᵈ give rise to dependent first-passage percolation in which the passage time along a path is the number of color changes. Under certain conditions, we prove strict positivity of the time constant (and a corresponding asymptotic shape result) by means of a theorem of Cox, Gandolfi, Griffin and Kesten about "greedy" lattice animals. Of particular interest are i.i.d. colorings and the $d = 2$ Ising model. We also apply the greedy lattice animal theorem to prove a result on the omnipresence of the infinite cluster in high density independent bond percolation.