SIAM Journal on Discrete Mathematics · 2017 · 12 citations · 22 references
Natural SciencesMathematicsCombinatoricsProbability TheoryStochastic ProcessesGraph TheoryMarkov ChainsExponential DecayGibbs DistributionGibbs SamplingGraph HomomorphismsWeak Mixing
Given a countable graph $\mathcal{G}$ and a finite graph $H$, we consider $Hom(\mathcal{G}, H)$ the set of graph homomorphisms from $\mathcal{G}$ to $H$ and we study Gibbs measures supported on $Hom(\mathcal{G}, H)$. We develop some sufficient and other necessary conditions for the existence of Gibbs specifications on $Hom(\mathcal{G}, H)$ satisfying strong spatial mixing (with exponential decay rate). We relate this with previous work of Brightwell and Winkler, who showed that a graph $H$ has a combinatorial property called dismantlability iff for every $\mathcal{G}$ of bounded degree, there exists a Gibbs specification with unique Gibbs measure. We strengthen their result by showing that such Gibbs specification can be chosen to have weak spatial mixing. In addition, we exhibit a subfamily of graphs $H$ for which there exists Gibbs specifications satisfying strong spatial mixing, but we also show that there exist dismantlable graphs for which no Gibbs specification has strong spatial mixing.
22
Incidence matrices and interval graphs
D. R. Fulkerson, Oliver Gross · Pacific Journal of Mathematics · 1965 · 1.3K citations · Full text
Vertex-to-vertex pursuit in a graph
Richard J. Nowakowski, Peter Winkler · Discrete Mathematics · 1983 · 600 citations
Counting independent sets up to the tree threshold
Dror Weitz · 2006 · 444 citations