Random Lipschitz functions on graphs with weak expansion
| Autor: | Işık, Senem, Park, Jinyoung |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | Benjamini, Yadin, and Yehudayoff (2007) showed that if the maximum degree of a graph $G$ is 'sub-logarithmic,' then the typical range of random $\mathbb Z$-homomorphisms is super-constant. Furthermore, they showed that there is a sharp transition on the range of random $\mathbb Z$-homomorphisms on the graph $C_{n,k}$, the tensor product of the $n$-cycle and the complete graph on $k$ vertices with self-loops, around $k=2\log n$. We extend (to some extent) their results to random $M$-Lipschitz functions and random real-valued Lipschitz functions. Comment: 16 pages, 1 figure |
| Databáze: | arXiv |
| Externí odkaz: |
|