Random Graph-Homomorphisms and Logarithmic Degree

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)$.