Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2604.03119 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908934971850752 |
|---|---|
| author | Dong, Dingding Park, Jinyoung |
| author_facet | Dong, Dingding Park, Jinyoung |
| contents | We prove that random $\mathbb{Z}$-homomorphisms on weakly expanding bipartite graphs exhibit a strong "flatness" phenomenon. Extending prior work of Peled, Samotij, and Yehudayoff for expanders, we first show that on any bipartite $(n, d, λ)$-graph with $λ\leq (1-δ)d$, a uniformly chosen $\mathbb{Z}$-homomorphism has a range at most $O(\log \log n)$ with high probability, which is tight up to a constant factor. This provides an affirmative answer to their question in the spectral setting. As a concrete application, we prove that a random $\mathbb{Z}$-homomorphism on the middle layers of the Hamming cube takes at most $5$ values with high probability. This shows that the $O(1)$-flatness for the full Hamming cube, proved by Kahn and Galvin, persists even when the rigid structural properties are relaxed. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_03119 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Range of random $\mathbb Z$-homomorphisms on weak expanders Dong, Dingding Park, Jinyoung Combinatorics We prove that random $\mathbb{Z}$-homomorphisms on weakly expanding bipartite graphs exhibit a strong "flatness" phenomenon. Extending prior work of Peled, Samotij, and Yehudayoff for expanders, we first show that on any bipartite $(n, d, λ)$-graph with $λ\leq (1-δ)d$, a uniformly chosen $\mathbb{Z}$-homomorphism has a range at most $O(\log \log n)$ with high probability, which is tight up to a constant factor. This provides an affirmative answer to their question in the spectral setting. As a concrete application, we prove that a random $\mathbb{Z}$-homomorphism on the middle layers of the Hamming cube takes at most $5$ values with high probability. This shows that the $O(1)$-flatness for the full Hamming cube, proved by Kahn and Galvin, persists even when the rigid structural properties are relaxed. |
| title | Range of random $\mathbb Z$-homomorphisms on weak expanders |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2604.03119 |