Range of random ℤ \mathbb{Z} -homomorphisms on weak expanders
Dingding Dong, Jinyoung Park · 2026
Read Range of random ℤ \mathbb{Z} -homomorphisms on weak expanders by Dingding Dong, Jinyoung Park (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-03119.txt.
Introduction
Dong and Park prove that random integer-valued homomorphisms on weakly expanding bipartite graphs stay remarkably flat. On any bipartite graph meeting their spectral condition, a random homomorphism takes at most a doubly logarithmic number of values with high probability, and the bound is tight up to a constant. On central Hamming-cube layers, the same phenomenon caps the range at 5 values.
Catalog record
| CREATOR | Dingding Dong, Jinyoung Park |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 94641 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.03119
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Range of random ℤ \mathbb{Z} -homomorphisms on weak expanders Dingding Dong, Jinyoung Park Abstract . 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 , λ ) (n,d,\lambda) -graph with λ ≤ ( 1 − δ ) d \lambda\leq(1-\delta)d , a uniformly chosen ℤ \mathbb{Z} -homomorphism has a range at most O ( log log n ) 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 5 values with high probability. This shows that the O ( 1 ) O(1) -flatness for the full Hamming cube, proved by Kahn and Galvin, persists even when the rigid structural properties are relaxed. 1. Introduction Discrete height functions, particularly integer-valued Lipschitz functions and \mathbb{Z} -homomorphisms on graphs, are widely studied at the intersection of combinatorics, probability, and statistical mechanics. The primary focus of this paper is the “flatness” phenomenon of random \mathbb{Z} -homomorphisms on weak expanders. Given a graph \Gamma , a \mathbb{Z} -homomorphism is a function h:V(\Gamma)\rightarrow\mathbb{Z} such that adjacent vertices receive adjacent integer values (i.e., |h(u)-h(v)|=1 for all edges \{u,v\} ). Clearly, such a function can only exist if the underlying graph \Gamma is bipartite. This framework provides a natural generalization of the simple random walk on \mathbb{Z} ; indeed, an n -step simple random walk corresponds exactly to a uniformly random \mathbb{Z} -homomorphism from a path of length n to \mathbb{Z} . Extending this probabilistic perspective, a uniformly random \mathbb{Z} -homomorphism from a general bipartite graph \Gamma , rooted by mapping a fixed vertex v_{0} to 0 , is also called a \Gamma -indexed random walk (see, e.g., [ 4 , 5 ] ). Formally, let \Gamma=(V,E) be a connected bipartite graph with vertex bipartition V=\mathcal{E}\cup\mathcal{O} . For a distinguished vertex v_{0}\in V , we define \mbox{\rm{Hom}}_{v_{0}}(\Gamma):=\{h:V\rightarrow\mathbb{Z}\mid h(v_{0})=0\text{ and }\{u,v\}\in E\implies|h(u)-h(v)|=1\}. We will call an element of \mbox{\rm{Hom}}_{v_{0}}(\Gamma) a rooted \mathbb{Z} -homomorphism from \Gamma (with respect to v_{0} ). Define the range of h\in\mbox{\rm{Hom}}_{v_{0}}(\Gamma) as R(h)=|\{h(x):x\in V\}|. 1.1. Main results Our first main result, 1.1 , concerns the typical range of \mathbb{Z} -homomorphisms on bipartite spectral expanders, and is motivated by a question raised by Peled, Samotij, and Yehudayoff [ 28 ] . As a slight variant of standard terminology, we define a bipartite (n,d,\lambda) -graph to be a d -regular bipartite graph with n vertices in each part, such that its second largest eigenvalue is at most \lambda . In [ 28 ] , Peled, Samotij, and Yehudayoff investigated the typical range of integer-valued Lipschitz functions and \mathbb{Z} -homomorphisms on expanders. Focusing on their results for \mathbb{Z} -homomorphisms, we note that they proved that if the underlying graph is a sufficiently strong expander—meaning the parameter \lambda is much smaller than the degree d , specifically \lambda\leq\frac{d}{300\log d} —then a typical \mathbb{Z} -homomorphism takes only O\left(\frac{\log\log n}{\log(d/\lambda)}\right) values with high probability. 1 1 1 To be precise, the notion of expanders used in [ 28 ] was defined via the Expander Mixing Lemma (EML) [ 1 ] : they defined a d -regular bipartite graph \Gamma with vertex bipartition \mathcal{E}\cup\mathcal{O} such that |\mathcal{E}|=|\mathcal{O}|=n to be a \lambda -expander if \left|e(S,T)-\frac{d}{n}|S||T|\right|\leq\lambda\sqrt{|S||T|}\quad\text{for all $S\subseteq\mathcal{E},T\subseteq\mathcal{O}$} . While the EML condition is sufficient in their strong expansion regime ( \lambda\ll d ), our focus on the much weaker expansion regime (where \lambda is close to d ) necessitates the standard algebraic definition of (bipartite) (n,d,\lambda) -graphs. See Remark 1.3 for more explanation. To understand this bound, it is helpful to compare it with the trivial upper bound. It is a standard fact that the diameter of a bipartite (n,d,\lambda) -graph is O\big(\frac{\log n}{\log(d/\lambda)}\big) . Since the values of a \mathbb{Z} -homomorphism change by exactly 1 along any edge, the range of any \mathbb{Z} -homomorphism is deterministically bounded by the diameter of the graph (plus one). Thus, the result of [ 28 ] shows a strong “flatness” phenomenon: the typical range is double-logarithmic in n , which is much smaller than the logarithmic diameter. Furthermore, this upper bound is tight: an earlier result by Benjamini, Yadin, and Yehudayoff [ 6 ] established a matching lower bound, proving that the typical range is indeed \Omega\big(\frac{\log\log n}{\log(d/\lambda)}\big) . Following their result, Peled, Samotij, and Yehudayoff naturally asked whether a similar flatness phenomenon continues to hold for graphs with a much smaller spectral gap (expansion), such as when \lambda=(1-\delta)d for small \delta>0 . Our first main theorem answers this question affirmatively: Theorem 1.1 . For every \delta>0 , there exist constants d_{0}=d_{0}(\delta)>0 and C=C(\delta)>0 such that the following holds. Let \Gamma be a bipartite (n,d,\lambda) -graph with vertex bipartition V(\Gamma)=\mathcal{E}\cup\mathcal{O} such that d\geq d_{0} and \lambda\leq(1-\delta)d . Fix any v_{0}\in\mathcal{E} . Let \mathbf{h} be a random \mathbb{Z} -homomorphism chosen uniformly from \mbox{\rm{Hom}}_{v_{0}}(\Gamma) . Then, with probability 1-o_{n}(1) , R(\mathbf{h})\leq C\log\log n. In 1.1 , we state the result for a fixed constant \delta>0 for clarity of presentation. However, our argument still holds even if \delta decays as a function of d (i.e., \delta=o_{d}(1) ). As a concrete application of our framework in the \delta=o_{d}(1) regime, our second main result, 1.2 , shifts the focus to a specific combinatorial structure: the middle layers of the Hamming cube. Our investigation in this setting is naturally motivated by two related lines of research. The first motivation is given by the study of the “flatness” of typical \mathbb{Z} -homomorphisms on the Hamming cube, Q_{d} . While the maximum possible range of a \mathbb{Z} -homomorphism on Q_{d} is trivially d+1 (its diameter plus one), it was initially conjectured in [ 4 ] that the typical range is sublinear, o(d) . Kahn [ 15 ] resolved this in a strong form, proving that the typical range is actually O(1) . Galvin [ 8 ] later improved this constant, demonstrating that a random \mathbb{Z} -homomorphism on Q_{d} takes at most 5 values with high probability. These results—later vastly generalized to high-dimensional tori by Peled [ 27 ] —show an extreme rigidity in the typical behavior of \mathbb{Z} -homomorphisms. Kahn’s proof makes crucial use of the sophisticated structure of the Hamming cube, and Galvin’s subsequent refinement builds on Kahn’s earlier work. Given the phenomenon explored by Peled, Samotij, and Yehudayoff [ 28 ] , a natural question arises: is this extreme strong flatness (taking only at most 5 values) a consequence of the rigid structure of the Hamming cube, or does it still hold in more general settings? To answer this, we turn to a natural testbed: the middle layers of the Hamming cube. While this specific subgraph has attracted independent interest (e.g. [ 2 , 3 , 7 , 11 , 23 ] ), for our present purposes, it provides a concrete setting to explore how much we can weaken the structural requirements. Before formally stating our result, we introduce some relevant definitions. Let Q_{2d-1} denote the (2d-1) -dimensional Hamming cube.