Random Graph-Homomorphisms and Logarithmic Degree
@article{EJP427,
author = {Itai Benjamini and Ariel Yadin and Amir Yehudayoff},
title = {Random Graph-Homomorphisms and Logarithmic Degree},
journal = {Electron. J. Probab.},
fjournal = {Electronic Journal of Probability},
volume = {12},
year = {2007},
keywords = {},
abstract = {A graph homomorphism between two graphs is a map from the vertex set of one graph to the vertex set of the other graph, that maps edges to edges. In this note we study the range of a uniformly chosen homomorphism from a graph $G$ to the infinite line $Z$. It is shown that if the maximal degree of $G$ is `sub-logarithmic', then the range of such a homomorphism is super-constant.
Furthermore, some examples are provided, suggesting that perhaps for graphs with super-logarithmic degree, the range of a typical homomorphism is bounded. In particular, a sharp transition is shown for a specific family of graphs $C_{n,k}$ (which is the tensor product of the $n$-cycle and a complete graph, with self-loops, of size $k$). That is, given any function $\psi(n)$ tending to infinity, the range of a typical homomorphism of $C_{n,k}$ is super-constant for $k= 2\log(n) - \psi(n)$, and is $3$ for $k= 2\log(n) + \psi(n)$.
},
pages = {no. 32, 926-950},
issn = {1083-6489},
doi = {10.1214/EJP.v12-427},
url = {http://ejp.ejpecp.org/article/view/427}}