Random graph-homomorphisms and logarithmic degree

DOI10.1214/EJP.V12-427zbMATH Open1127.60007arXivmath/0611416MaRDI QIDQ2461995FDOQ2461995

Authors: Itai Benjamini, Ariel Yadin, Amir Yehudayoff 

Publication date: 23 November 2007

Published in: Electronic Journal of Probability (Search for Journal in Brave)

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

Full work available at URL: https://arxiv.org/abs/math/0611416

Recommendations

• A note on random homomorphism from arbitrary graphs to \(\mathbb{Z}\)
• On random graph homomorphisms into \({\mathbb{Z}}\)
• Distinct degrees and homogeneous sets
• Extremal H‐Colorings of Graphs with Fixed Minimum Degree
• Inequalities with respect to graph homomorphism

zbMATH Keywords

graph indexed random walkgraphs with super-logarithmic degree

Mathematics Subject Classification ID

Combinatorial probability (60C05)

Cited In (12)

• On the distribution of range for tree-indexed random walks
• Random mappings of scaled graphs.
• Height function localisation on trees
• Diffusivity of a random walk on random walks
• A note on random homomorphism from arbitrary graphs to \(\mathbb{Z}\)
• Law of the iterated logarithm for random graphs
• Lipschitz functions on expanders are typically flat
• Delocalization of two-dimensional random surfaces with hard-core constraints
• A note on Random Homomorphism from ArbitraryGraphs to Z
• Delocalization of uniform graph homomorphisms from \({\mathbb{Z}}^2\) to \({\mathbb{Z}} \)
• The Grothendieck constant of random and pseudo-random graphs
• Logarithmic variance for the height function of square-ice

This page was built for publication: Random graph-homomorphisms and logarithmic degree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2461995)