 |
|
|
| | | | | |
|
|
|
|
|
Random Graph-Homomorphisms and Logarithmic Degree
|
Itai Benjamini, Weizmann Institute
Ariel Yadin, Weizmann Institute
Amir Yehudayoff, Weizmann Institute
|
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 Cn,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 ψ(n) tending to infinity, the range of a typical homomorphism of Cn,k is super-constant for k = 2 log(n) - ψ(n), and is 3 for k = 2 log(n) + ψ(n)
|
Full text: PDF
Pages: 926-950
Published on: June 19, 2007
|
Bibliography
-
I. Benjamini, O. Haggstrom, E. Mossel.
On random graph homomorphisms into Z, Journal of
Combinatorial Theory (Series B) 78 (2000), 86--114.
Math. Review 2001c:60135
-
I. Benjamini, Y. Peres. Tree-indexed random
walks on groups and first passage percolation, Probability Theory
and Related Fields, 98 (1994), 91--112.
Math. Review 94m:60141
-
I. Benjamini, G. Schechtman.
Upper bounds on the height difference
of the Gaussian random field and the range of random graph
homomorphism into Z, Random Structures & Algorithms 17
(2000), 20--25.
Math. Review 2002c:05137
-
D. Galvin. On homomorphisms from the
Hamming cube to Z, Israel Journal of Mathematics 138 (2003), 189--213.
Math. Review 2005b:05158
-
O. Gurel-Gurevich. private communication.
-
J. Kahn. Range of cube-indexed random walks,
Israel Journal of Mathematics 124 (2001), 189--201.
Math. Review 2002k:60173
-
R. Kenyon, Dominos and the Gaussian free field, Ann. Prob. 29
no. 3 (2001), 1128--1137.
Math. Review 2002k:82039
-
M. Loebl, J. Nesetril, B. Reed. A note on random homomorphism from arbitrary graphs to
Z, Discrete Mathematics 273 no. 1 (2003), 173--181.
Math. Review 2004k:05176
-
S. Sheffield. Random Surfaces, Asterisque no. 304 (2005).
Math. Review 2007g:82021
|
|
|
|
|
|
|
|
| | | | |
Electronic Journal of Probability. ISSN: 1083-6489 |
|
Context