Random graph-homomorphisms and logarithmic degree
From MaRDI portal
Publication:2461995
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).
Recommendations
Cited in
(12)- Logarithmic variance for the height function of square-ice
- Delocalization of uniform graph homomorphisms from \({\mathbb{Z}}^2\) to \({\mathbb{Z}} \)
- A note on Random Homomorphism from ArbitraryGraphs to Z
- Diffusivity of a random walk on random walks
- Delocalization of two-dimensional random surfaces with hard-core constraints
- Height function localisation on trees
- Lipschitz functions on expanders are typically flat
- The Grothendieck constant of random and pseudo-random graphs
- On the distribution of range for tree-indexed random walks
- Law of the iterated logarithm for random graphs
- Random mappings of scaled graphs.
- A note on random homomorphism from arbitrary graphs to \(\mathbb{Z}\)
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)
