2010/07/27 by David Galvin, Galvin, David, Fabio Martinelli +5 · 1 citation
Computer Science · Mathematics · #05C99 #60K35 #82B20 #82B26 #Advanced Graph Theory Research #FOS: Mathematics #FOS: Physical sciences #Graph theory and applications #Markov Chains and Monte Carlo Methods #Mathematical Physics (math-ph) #Probability (math.PR) #secondary: 90B15
paper · pdf · doi:10.48550/arxiv.1007.4806
openalex publication_date 2010/07/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The classical hard core model from statistical physics, with activity λ> 0 and capacity C=1, on a graph G, concerns a probability measure on the set \mathcal I(G) of independent sets of G, with the measure of each independent set I ∈ \mathcal I(G) being proportional to λ|I|. Ramanan et al. proposed a generalization of the hard core model as an idealized model of multicasting in communication networks. In this generalization, the \em multi-state hard core model, the capacity C is allowed to be a positive integer, and a configuration in the model is an assignment of states from \0,…,C\ to V(G) (the set of nodes of G) subject to the constraint that the states of adjacent nodes may not sum to more than C. The activity associated to state i is λi, so that the probability of a configuration σ:V(G)→ \0,…, C\ is proportional to λ^∑v ∈ V(G) σ(v). In this work, we consider this generalization when G is an infinite rooted b-ary tree and prove rigorously some of the conjectures made by Ramanan et al. In particular, we show that the C=2 model exhibits a (first-order) phase transition at a larger value of λ than the C=1 model exhibits its (second-order) phase transition. In addition, for large b we identify a short interval of values for λ above which the model exhibits phase co-existence and below which there is phase uniqueness. For odd C, this transition occurs in the region of λ= (e/b)^1/\ceilC/2, while for even C, it occurs around λ=(log b/b(C+2))2/(C+2). In the latter case, the transition is first-order.