Random Graph-Homomorphisms and Logarithmic Degree
| dc.creator | Benjamini, Itai | |
| dc.creator | Yadin, Ariel | |
| dc.creator | Yehudayoff, Amir | |
| dc.date | 2006-11-14 | |
| dc.date | 2007-06-21 | |
| dc.date.accessioned | 2026-07-07T08:11:26Z | |
| dc.date.available | 2026-07-07T08:11:26Z | |
| dc.description | 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). | |
| dc.identifier | https://arxiv.org/abs/math/0611416 | |
| dc.identifier | http://arxiv.org/abs/math/0611416 | |
| dc.identifier | Electronic Journal of Probability, 12 (2007), 926--950 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/132121 | |
| dc.subject | Probability | |
| dc.subject | Mathematical Physics | |
| dc.subject | Combinatorics | |
| dc.subject | 60C05 | |
| dc.title | Random Graph-Homomorphisms and Logarithmic Degree | |
| dc.type | text |