pith. sign in

arxiv: 2604.03119 · v1 · submitted 2026-04-03 · 🧮 math.CO

Range of random mathbb Z-homomorphisms on weak expanders

Dingding Dong , Jinyoung Park This is my paper

Pith reviewed 2026-05-13 18:19 UTC · model grok-4.3

classification 🧮 math.CO
keywords random Z-homomorphismsweak expandersspectral expansionbipartite graphsrange of homomorphismsHamming cubeflatness
0
0 comments X

The pith

A random Z-homomorphism on a weakly expanding bipartite graph takes only O(log log n) values with high probability.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that random integer-valued homomorphisms on bipartite graphs satisfying a modest spectral expansion condition are highly concentrated in their values. Under the assumption that the second eigenvalue is at most a (1-δ) fraction of the degree, the range is bounded by O(log log n) with high probability, and this bound is tight up to constants. The result extends earlier flatness theorems from strong expanders to this weaker setting and applies directly to show that the same phenomenon holds on the middle layers of the Hamming cube, where the range is at most 5 with high probability.

Core claim

On any bipartite (n, d, λ)-graph with λ ≤ (1-δ)d, a uniformly chosen Z-homomorphism has range at most O(log log n) with high probability. This is tight up to a constant factor and answers a question of Peled, Samotij, and Yehudayoff in the spectral setting. As a concrete application, a random Z-homomorphism on the middle layers of the Hamming cube takes at most 5 values with high probability.

What carries the argument

The spectral expansion condition λ ≤ (1-δ)d on a bipartite (n, d, λ)-graph, which limits the spread of values under a random Z-homomorphism.

If this is right

  • The flatness bound extends from strong expanders to all bipartite graphs meeting the weaker spectral threshold.
  • Random Z-homomorphisms on the middle layers of the Hamming cube are at most 5-valued with high probability.
  • The O(log log n) upper bound is asymptotically tight for some sequences of weak expanders.
  • The result supplies an affirmative answer to the question posed by Peled, Samotij, and Yehudayoff in the spectral setting.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Spectral expansion by itself appears sufficient for the flatness phenomenon, without needing additional symmetry or rigidity.
  • Similar concentration may hold for other random labelings on graphs whose expansion is controlled only spectrally.
  • The constant bound of 5 on the cube middle layers suggests that flatness survives even when the host graph is induced and far from regular.
  • The technique may yield range bounds for random homomorphisms into other groups on the same class of graphs.

Load-bearing premise

The input graph must be bipartite and satisfy the spectral condition that its second eigenvalue is bounded away from the degree by a fixed positive fraction.

What would settle it

Identifying a bipartite graph with λ ≤ (1-δ)d on which a positive fraction of Z-homomorphisms have range larger than C log log n for some large constant C.

read the original 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, \lambda)$-graph with $\lambda \leq (1-\delta)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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper proves that on any bipartite (n,d,λ)-graph with λ ≤ (1-δ)d, a uniformly random ℤ-homomorphism has range O(log log n) with high probability; the bound is tight up to a constant factor. This extends the Peled-Samotij-Yehudayoff result from strong expanders to the spectral setting and affirmatively answers their question. As an application, random ℤ-homomorphisms on the middle layers of the Hamming cube take at most 5 values whp, showing that the O(1)-flatness of Kahn-Galvin persists under relaxed structure.

Significance. If the central derivation holds, the result is significant: it shows the flatness phenomenon for random ℤ-homomorphisms is robust to replacing strong expansion by a constant-factor spectral gap, and the explicit Hamming-cube application demonstrates that the phenomenon survives removal of the cube's rigid layer structure. The tightness construction is a concrete strength.

major comments (2)
  1. [§3] §3 (iterative mixing argument): the number of rounds needed to bound the range by O(log log n) must be shown to depend only on δ and not on n; the current sketch leaves the failure probability per round implicit and does not verify that the union bound over O(log log n) rounds remains o(1).
  2. [Theorem 1.2] Theorem 1.2 (Hamming-cube application): the claim that the middle-layer graph satisfies λ ≤ (1-δ)d with δ bounded away from zero requires an explicit spectral-gap calculation; without it the reduction to the main theorem is incomplete.
minor comments (2)
  1. [Abstract] The abstract states the range bound is 'tight up to a constant factor' but does not name the matching lower-bound construction; add a forward reference to the explicit example in §5.
  2. [§2] Notation for the (n,d,λ)-graph should be recalled at the start of §2 to avoid forward references from the introduction.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading, the positive assessment of the results, and the recommendation for minor revision. We address the two major comments point by point below. Both points identify places where the current write-up is insufficiently explicit, and we will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [§3] §3 (iterative mixing argument): the number of rounds needed to bound the range by O(log log n) must be shown to depend only on δ and not on n; the current sketch leaves the failure probability per round implicit and does not verify that the union bound over O(log log n) rounds remains o(1).

    Authors: We agree that the dependence on δ must be made fully explicit. The iterative argument proceeds in t = C_δ log log n rounds for a constant C_δ that depends only on the relative gap δ (via the contraction factor λ/d ≤ 1-δ in the relevant mixing lemma). Each round fails with probability at most exp(-c_δ n) for some c_δ > 0 that likewise depends only on δ; this follows from the standard Chernoff bound on the number of vertices whose homomorphism value changes by more than 1, which is controlled by the spectral assumption. The union bound over t rounds is therefore at most t exp(-c_δ n) = o(1) as n → ∞. We will insert the explicit statements of t = O_δ(log log n), the per-round failure probability, and the union-bound verification into the revised §3. revision: yes

  2. Referee: [Theorem 1.2] Theorem 1.2 (Hamming-cube application): the claim that the middle-layer graph satisfies λ ≤ (1-δ)d with δ bounded away from zero requires an explicit spectral-gap calculation; without it the reduction to the main theorem is incomplete.

    Authors: We will add an explicit computation of the second-largest eigenvalue of the middle-layer graph. Let G be the bipartite graph with parts consisting of all vectors in {0,1}^n of Hamming weight ⌊n/2⌋ and ⌈n/2⌉, with edges between vectors differing in exactly one coordinate. This graph is a regular induced subgraph of the hypercube. Its adjacency operator can be diagonalized using the Krawtchouk polynomials restricted to the middle layers; the resulting eigenvalues satisfy λ_2(G) ≤ (1 - c)d for an absolute constant c > 0 independent of n (the gap is inherited from the hypercube's constant gap and the concentration of the middle layers). We will include the short derivation in the revised version of the paper, thereby making the reduction to Theorem 1.1 fully self-contained. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The derivation extends the Peled-Samotij-Yehudayoff theorems on expanders by introducing a new spectral-gap argument that controls the spread of a uniform random Z-homomorphism via iterative mixing over the bipartition under the assumption λ ≤ (1-δ)d. The O(log log n) range bound is obtained from O(log log n) rounds of measure control and does not reduce to any fitted parameter, self-definition, or self-citation chain. The Hamming-cube application follows once the middle-layer graph is verified to satisfy the same gap condition with δ bounded away from zero. All load-bearing steps rely on external prior results by different authors and on the explicit (n,d,λ) definition; no step collapses to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The proof relies on standard spectral graph theory, the probabilistic method, and the definition of Z-homomorphisms; no new free parameters, ad-hoc axioms, or invented entities are introduced in the abstract.

axioms (2)
  • standard math Standard facts from spectral graph theory relating the second eigenvalue to expansion
    Invoked to control the spread of the random homomorphism under the given λ bound.
  • domain assumption Existence and uniformity of random Z-homomorphisms on bipartite graphs
    Used throughout the statement of the main theorem.

pith-pipeline@v0.9.0 · 5459 in / 1387 out tokens · 20033 ms · 2026-05-13T18:19:46.932017+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

35 extracted references · 35 canonical work pages

  1. [1]

    Alon and F

    N. Alon and F. R. K. Chung. Explicit construction of linear sized tolerant networks.Discrete Mathematics, 72(1-3):15–19, 1988. 2, 4

    work page 1988

  2. [2]

    Balogh, C

    J. Balogh, C. Chen, and R. I. Garcia. Maximal independent sets in the middle two layers of the boolean lattice.arXiv preprint arXiv:2505.00132, 2025. 2, 3

    work page arXiv 2025

  3. [3]

    Balogh, R

    J. Balogh, R. I. Garcia, and L. Li. Independent sets in the middle two layers of boolean lattice.Journal of Combinatorial Theory, Series A, 178:105341, 2021. 2, 3

    work page 2021

  4. [4]

    Benjamini, O

    I. Benjamini, O. H ¨aggstr¨om, and E. Mossel. On random graph homomorphisms intoZ.Journal of Combinatorial Theory, Series B, 78(1):86–114, 2000. 1, 2

    work page 2000

  5. [5]

    Benjamini and Y

    I. Benjamini and Y. Peres. Tree-indexed random walks on groups and first passage percolation.Probability Theory and Related Fields, 98:91–112, 1994. 1

    work page 1994

  6. [6]

    Benjamini, A

    I. Benjamini, A. Yadin, and A. Yehudayoff. Random graph-homomorphisms and logarithmic degree.Electronic Journal of Probabil- ity, 12:926–950, 2007. 2

    work page 2007

  7. [7]

    Duffus, P

    D. Duffus, P . Frankl, and V . R ¨odl. Maximal independent sets in the covering graph of the cube.Discrete applied mathematics, 161(9):1203–1208, 2013. 2

    work page 2013

  8. [8]

    D. Galvin. On homomorphisms from the hamming cube toZ.Israel Journal of Mathematics, 138:189–213, 2003. 2, 3, 4, 7, 8, 10

    work page 2003

  9. [9]

    D. Galvin. Independent sets in the discrete hypercube.arXiv preprint arXiv:1901.01991, 2019. 8, 23

    work page arXiv 1901

  10. [10]

    Hoory, N

    S. Hoory, N. Linial, and A. Wigderson. Expander graphs and their applications.Bulletin of the American Mathematical Society, 43(4):439–561, 2006. 6

    work page 2006

  11. [11]

    Ilinca and J

    L. Ilinca and J. Kahn. Counting maximal antichains and independent sets.Order, 30(2):427–435, 2013. 2

    work page 2013

  12. [12]

    Jenssen and P

    M. Jenssen and P . Keevash. Homomorphisms from the torus.Advances in Mathematics, 430:109212, 2023. 3

    work page 2023

  13. [13]

    Jenssen, J

    M. Jenssen, J. Park, and A. Malekshahian. On dedekind’s problem, a sparse version of sperner’s theorem, and antichains of a given size in the boolean lattice.arXiv preprint arXiv:2411.03400, 2024. 3

    work page arXiv 2024

  14. [14]

    Jenssen and W

    M. Jenssen and W. Perkins. Independent sets in the hypercube revisited.Journal of the London Mathematical Society, 102(2):645–669,

    work page

  15. [15]

    J. Kahn. Range of cube-indexed random walk.Israel Journal of Mathematics, 124:189–201, 2001. 2, 3

    work page 2001

  16. [16]

    Kahn and J

    J. Kahn and J. Park. The number of 4-colorings of the hamming cube.Israel Journal of Mathematics, 236(2):629–649, 2020. 3

    work page 2020

  17. [17]

    Kahn and J

    J. Kahn and J. Park. The number of maximal independent sets in the hamming cube.Combinatorica, 42(6):853–880, 2022. 3

    work page 2022

  18. [18]

    G. Katona. A theorem of finite sets. InClassic Papers in Combinatorics, pages 381–401. Springer, 1968. 7

    work page 1968

  19. [19]

    D. E. Knuth. The art of computer programming, vol 1: Fundamental.Algorithms. Reading, MA: Addison-Wesley, 1968. 5

    work page 1968

  20. [20]

    A. D. Korshunov and A. A. Sapozhenko. The number of binary codes with distance 2.Problemy Kibernet, 40:111–130, 1983. 4

    work page 1983

  21. [21]

    R. A. Krueger, L. Li, and J. Park. Lipschitz functions on weak expanders.arXiv preprint arXiv:2408.14702, 2024. 3, 4

    work page arXiv 2024

  22. [22]

    J. B. Kruskal. The number of simplices in a complex.Mathematical optimization techniques, 10:251–278, 1963. 7

    work page 1963

  23. [23]

    L. Li, G. McKinley, and J. Park. The number of colorings of the middle layers of the Hamming cube.arXiv preprint arXiv:2304.03203, 2023. 2, 3

    work page arXiv 2023

  24. [24]

    Lov ´asz

    L. Lov ´asz. On the ratio of optimal integral and fractional covers.Discrete Mathematics,13(4):383–390, 1975. 5

    work page 1975

  25. [25]

    Lov ´asz.Combinatorial problems and exercises, volume 361

    L. Lov ´asz.Combinatorial problems and exercises, volume 361. American Mathematical Soc., 2007. 7

    work page 2007

  26. [26]

    R. Peierls. On ising’s model of ferromagnetism.Mathematical Proceedings of the Cambridge Philosophical Society, 32(3):477–481, 1936. 4

    work page 1936

  27. [27]

    R. Peled. High-dimensional lipschitz functions are typically flat.The Annals of Probability, 45(3):1351–1447, 2017. 2

    work page 2017

  28. [28]

    Peled, W

    R. Peled, W. Samotij, and A. Yehudayoff. Lipschitz functions on expanders are typically flat.Combinatorics, Probability and Com- puting, 22(4):566–591, 2013. 1, 2, 3, 4, 10

    work page 2013

  29. [29]

    A. A. Sapozhenko. On the number of connected subsets with given cardinality of the boundary in bipartite graphs.Metody Diskret. Analiz, 45(45):42–70, 1987. 7

    work page 1987

  30. [30]

    A. A. Sapozhenko. The number of antichains in ranked posets.Discrete Math. Appl.,1(1):35–58, 1991. 3 RANGE OF RANDOMZ-HOMOMORPHISMS ON WEAK EXPANDERS 21

    work page 1991

  31. [31]

    A. A. Sapozhenko. On the number of antichains in multilevelled ranked posets.Discrete Math. Appl.,1(2):149–169, 1991. 3

    work page 1991

  32. [32]

    R. P . Stanley.Algebraic Combinatorics: Walks, Trees, Tableaux, and More. Springer, 2013. See Chapter 2 for the spectrum of the up and down operators on the Boolean lattice. 3

    work page 2013

  33. [33]

    S. K. Stein. Two combinatorial covering theorems.J. Comb. Theory, Ser. A,16:391–397, 1974. 5

    work page 1974

  34. [34]

    analogous

    R. M. Tanner. Explicit concentrators from generalized n-gons.SIAM Journal on Algebraic Discrete Methods, 5(3):287–293, 1984. 6 APPENDIXA. PROOF OFLEMMA3.4 Lemma(Lemma 3.4).LetΓbe a bipartited-regular graph with vertex bipartitionV(Γ) =E ∪ O. Fixb≤h≤ a′ ≤gandv∈ O. Then there exists a family Uquad(a′, g, b, h, v)⊆2 O ×2 E ×2 E ×2 O with |Uquad(a′, g, b, h, ...

    work page 1984

  35. [35]

    analogous

    LetT 1 ⊆G\Lbe a minimum cover (see Definition 2.3) of[A]\N(L)inQ 2d−1. Take F ′ =L∪T 1. We first verify thatF ′ is aϕ-approximation (Definition B.1) ofA: •ClearlyG ϕ ⊆L⊆F ′. •AlsoT ′ 0 ⊆G ϕ,N(N [A](T0))⊆G, andT 1 ⊆G, soF ′ ⊆G. •AlsoN(T 1)⊇[A]\N(L), soN(F ′)⊇[A]. We then make the following two observations: •F ′ is 4-linked. This is because every vertex in...

    work page