Random Graph-Homomorphisms and Logarithmic Degree
Authors:
Open Access
- 1 January 2007
- journal article
- Published by Institute of Mathematical Statistics in Electronic Journal of Probability
- Vol. 12 (none) , 926-950
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)$.
Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- A note on random homomorphism from arbitrary graphs to ZDiscrete Mathematics, 2003
- On homomorphisms from the Hamming cube to ZIsrael Journal of Mathematics, 2003
- Range of cube-indexed random walkIsrael Journal of Mathematics, 2001
- Dominos and the Gaussian Free FieldThe Annals of Probability, 2001
- Upper bounds on the height difference of the Gaussian random field and the range of random graph homomorphisms into ?Random Structures & Algorithms, 2000
- On Random Graph Homomorphisms into ZJournal of Combinatorial Theory, Series B, 2000
- Tree-indexed random walks on groups and first passage percolationProbability Theory and Related Fields, 1994