Random Lipschitz functions on graphs with weak expansion

Jinyoung Park; Senem I\c{s}{\i}k

REVIEW 2 major objections 4 minor 11 references

Random Lipschitz functions on graphs with weak expansion

T0 review · 2 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read On graphs whose radius-$(r-1)$ balls are at most $c \log n$ in size, a uniformly random $M$-Lipschitz function has range at least $M r/2$ with high probability, for every $M$.

desk verdict Solid extension of BYY to arbitrary M and a genuine multicolor entropy argument for C_{n,k}; the main theorems are likely correct, with a localized r=1 gap in Theorem 1.1 that should be fixable. read the letter →

arxiv 2411.09640 v1 pith:5APXCOHA submitted 2024-11-14 math.PR math-phmath.COmath.MP

Senem Iş{i}k , Jinyoung Park This is my paper · ORCID

classification math.PRmath-phmath.COmath.MP MSC 60C0505C8005C12

keywords randomLipschitzfunctionsweakexpansionrangeentropymethodZ-homomorphismsC_{nk}layeredgraphlogarithmicdegreehomomorphisms

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper proves that on a connected graph where all balls of radius $r-1$ have size at most a constant times $\log n$, a uniformly random $M$-Lipschitz function $f$ with $f(v_0)=0$ has range at least $M r/2$ with probability tending to 1, uniformly in $M$. This extends a 2007 result for $\mathbb{Z}$-homomorphisms to all $M$-Lipschitz functions, including $M$ that grows with $n$, and via an $M\to\infty$ limit it transfers to real-valued $1$-Lipschitz functions. On the layered graph $C_{n,k}$ — a cycle of $n$ layers, each with $k$ vertices, connected to neighboring layers by complete bipartite graphs — the paper shows the opposite phenomenon: once $k$ exceeds $\gamma M^2 \log(Mn)$, the range of a uniform $M$-Lipschitz function is at most $M+1$ with probability $1 - O(1/\gamma)$, and with probability $1 - o_n(1)$ when $\log M = o(\log n)$. Together these give a picture of when random Lipschitz functions fluctuate: weak local growth forces large fluctuation, while sufficiently large layers with logarithmic degree force flatness.

What carries the argument

The mechanism for the weak-expansion theorem is a counting lemma (Lemma 3.2): for any ball $B$ of exact radius $r$ with boundary $\Gamma$, and any $M$-Lipschitz boundary condition on $\Gamma$, the fraction of functions on $B$ whose maximum reaches $M r/2$ is at least $C^{-m}$, where $m$ is the maximum size of a radius-$(r-1)$ ball. Combined with the disjoint-ball lemma (Lemma 3.1) from the earlier $\mathbb{Z}$-homomorphism work, this turns the failure of all disjoint balls to reach height $M r/2$ into an exponentially small probability. The mechanism for the flatness theorem is an entropy upper bound on the random function using the weighted entropy inequality of Lemma 2.2 with a layer ordering on $C_{n,k}$; it shows that unless each neighborhood's interval of attained values has length $M+1$, the entropy of $f$ is too small to match the trivial lower bound, forcing the range to stay at most $M+1$ along a cycle that traverses all layers.

What would settle it

On $C_{n,k}$ with $M=2$ and $n$ large, choose $k = \gamma \cdot 4 \log(2n)$ for a constant $\gamma$ just above $C$. Compute exactly (or by transfer matrix) the probability that a uniform $2$-Lipschitz function has range at most $3$; if this probability is not at least $1 - O(1/\gamma)$, Theorem 1.7 is false.

Watch

Extended reading notes

Core claim

The central claim is a pair of complementary statements about the typical range $R(f)$ of a uniform $M$-Lipschitz function. Theorem 1.1 says that if $\max_v |B_{r-1}(v)| \le c \log n$, then $P(R(f) < M r/2) = o_n(1)$ for every $M$; the proof works by partitioning the graph into many disjoint balls of exact radius $r$ and showing, via a new conditional count (Lemma 3.2), that on each ball the boundary conditions leave enough freedom to push the function up to height $M r/2$. Theorem 1.7 says that on $C_{n,k}$ with $k > \gamma M^2 \log(Mn)$, a random $M$-Lipschitz function has range at most $M+1$ with probability $1 - O(1/\gamma)$; the proof adapts the entropy argument used for cube-indexed random walks to graphs of logarithmic degree and large diameter, where neighborhoods need not be monochromatic and the number of 'colors' can grow with $n$ and $M$.

Load-bearing premise

The proof of Theorem 1.1 assumes that balls of radius $r$ are not much larger than balls of radius $r-1$, because the disjoint-ball argument is run with the radius-$r$ size while the theorem's hypothesis only bounds the radius-$(r-1)$ size; this gap is harmless for $r \ge 2$ but unaddressed for $r=1$.

Editorial extensions

If this is right

Any graph with maximum degree $d$ has, for every $M$, a uniform $M$-Lipschitz function whose range is at least $c M \log\log n / \log d$ with high probability; the real-valued analogue replaces $M$ by 1.
For expanders satisfying the known upper-bound hypotheses, the new lower bound and the upper bound together determine the order of the range, $\Theta(M \log\log n / \log(d/\lambda))$, with high probability.
Because Theorem 1.1 holds for every $M$, the large-fluctuation behavior on weak expanders does not change when $M$ exceeds the degree, settling a question left open in the expander literature.
On $C_{n,k}$, flatness is guaranteed once $k > \gamma M^2 \log(Mn)$, while an example in the paper shows flatness fails when $k \le (M/2)\ln(Mn)$; the true threshold in $k$ therefore lies between $M\log(Mn)$ and $M^2\log(Mn)$.
Theorem 1.3 transfers all of these conclusions to the real-valued model, whose uniform measure is the weak limit of scaled integer $M$-Lipschitz measures.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The gap between the flatness condition $k > \gamma M^2 \log(Mn)$ and the non-flatness example $k \le (M/2)\ln(Mn)$ suggests the sharp threshold on $C_{n,k}$ is likely near $k \approx M \log(Mn)$; a refined entropy argument that avoids losing one power of $M$ should close the gap.
The weak-expansion theorem's use of radius-$(r-1)$ balls rather than radius-$r$ balls hints that the right general hypothesis may be a bound on the product of the maximum degree and the radius-$(r-1)$ ball size; testing $r=1$ on non-regular graphs would show whether the missing case is a proof artifact or a genuine restriction.
The layer-by-layer interval-length control used on $C_{n,k}$ could serve as a template for other logarithmic-degree graphs with large diameter, such as tori or Cartesian products, where the original cube-entropy argument fails because neighborhoods have many colors.
Because the real-valued model is the weak limit of the integer $M$-Lipschitz models, a sharp threshold on $C_{n,k}$ for integer $M$ would transfer to a sharp threshold for the continuous model by the same scaling.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Short version: this is a real contribution, and the main results are probably right. Theorem 1.1 extends the Benjamini–Yadin–Yehudayoff lower bound from Z-homomorphisms to arbitrary M, including M tending to infinity, and Theorem 1.7 gives a multicolor version of Kahn's entropy argument on C_{n,k} with threshold k ≈ M^2 log(Mn). The proofs are serious and mostly well executed.

The heart of the paper is Lemma 3.2, which controls the probability that the center of a ball of exact radius r takes a high value under an arbitrary boundary condition. The proof partitions the ball into sets A and Q* and shifts values layer by layer; the count is uniform in M. That is genuinely new. Theorem 1.7's entropy argument is also new: it manages a non-constant number of colors, which the Engbers–Galvin extension did not allow.

Now the soft spots. The proof of Theorem 1.1 has a parameter mismatch: the hypothesis bounds max|B_{r−1}|, but Lemma 3.1 is applied with the maximum size of balls of radius r. For r=1, and generally when high-degree vertices make B_r much larger than B_{r−1}, the lemma does not guarantee the number of disjoint balls needed, and the final exponential bound can fail. This looks fixable (add a separate argument for r=1, or state the theorem with max|B_r| in the hypothesis), but as written it is a gap. The r=1 case is the only one affected; the corollaries use r≥2. Proposition 4.1 is imported from [10]; a proof or a precise statement would be better, but this is minor.

One thing I checked specifically: the stress-test concern about Lemma 5.1. It says the pinned measure is not vertex-transitive, so a single ε cannot serve both the entropy upper bound and the union bound. That concern is wrong. Even though the measure fixes f(v0)=0, for any automorphism φ the map f ↦ f∘φ − f(φ(v0)) is a bijection from Lip_{v0} to itself and preserves the uniform measure. The event |f̄_{N_v^+}| = M+1 only depends on the size of the image set, which is invariant under global shifts. So the probability is indeed the same for every v. The proof should say this; 'by symmetry' is too terse and invites this exact objection. But the argument itself is sound.

Bottom line: the paper deserves a serious referee. The r=1 gap should be addressed, and the symmetry argument in Lemma 5.1 should be written out. For anyone working on random Lipschitz functions or entropy bounds for graph homomorphisms, this is worth reading.

Referee Report

2 major / 4 minor

Summary. The paper studies the typical range of uniformly random M-Lipschitz functions (and, by scaling, real-valued 1-Lipschitz functions) on finite graphs, extending results of Benjamini, Yadin, and Yehudayoff for Z-homomorphisms. Theorem 1.1 gives a lower bound on the range under a small-ball condition max_v |B_{r-1}(v)| ≤ c log n, uniformly in M; Theorem 1.3 transfers this to real-valued Lipschitz functions; Theorem 1.7 gives an upper bound on the range for random M-Lipschitz functions on the layered graph C_{n,k}, showing flatness when k > γ M^2 log(Mn). The lower-bound proof uses a ball-counting lemma from [3] and a new construction (Lemma 3.4), while the upper-bound proof adapts Kahn's entropy method via Shearer's lemma.

Significance. If the proofs can be completed, the results constitute a genuine extension of the Benjamini-Yadin-Yehudayoff transition from Z-homomorphisms to arbitrary M-Lipschitz and real-valued Lipschitz functions. The uniform-in-M nature of Theorem 1.1 is a notable strength, as is the attempt to push Kahn's entropy argument beyond the monochromatic-neighborhood setting. The paper is clearly organized and provides helpful proof sketches. However, two load-bearing gaps, described below, mean that the main theorems are not established as written.

major comments (2)

[Section 3.2, proof of Theorem 1.1] The proof of Theorem 1.1 sets k = ⌊n/m^2⌋−1 with m = max_v |B_{r-1}(v)|, and then cites Lemma 3.1 to obtain k pairwise disjoint balls of exact radius r. However, Lemma 3.1 uses m(G,r) = max_v |B_r(v)|, which is not controlled by the theorem's hypothesis on |B_{r-1}|. When B_r(v) is much larger than B_{r-1}(v) (for example when r=1, or when high-degree vertices make B_r large), the number of disjoint exact-radius-r balls guaranteed by Lemma 3.1 can be far smaller than k, and the estimate k C^{-m} → ∞ in (13) no longer follows. This is a load-bearing gap in the proof as written; the applications with bounded degree may escape it, but the stated theorem covers all graphs.
[Section 5, Lemma 5.1 and derivation of Theorem 1.7] The assertion in Lemma 5.1 that 'by symmetry of C_{n,k}, the above probability is equal for any vertices' is not justified for the pinned uniform measure on Lip_v0(C_{n,k};M). The stabilizer of v0 preserves distance from v0, so it does not act transitively on vertices in different layers; already on C_{4,k} with M=1, vertices in L1 and L2 have different marginal fluctuation statistics. Consequently, a single ε in (22) cannot simultaneously serve as the per-vertex probability in the union bound (21) (where a maximum over vertices is needed) and as the common probability in the entropy upper bound (27) (where the expression N/2[(1−ε)log(M+1)^2 + ε log M(M+2)] requires an average over even vertices). If ε is taken as the maximum, the entropy replacement in (27) is invalid because log(M+1)^2 > log M(M+2), making the displayed expression a lower bound rather than an upper bound for the exact average term. The proof therefore does not establish the per-vertex bound (19) from the entropy estimate, and the proof of Theorem 1.7 is incomplete.

minor comments (4)

[Abstract and Introduction] There is a typo in the introduction: 'ths result there was recently improved' should read 'the result there was recently improved'.
[Throughout] The notation 'on(1)' is nonstandard; it should be typeset as 'o_n(1)' to match the definition given in the introduction.
[Lemma 3.2] In the statement of Lemma 3.2, 'm = m(G, r)' is confusing because the text defines it as the maximum size of a ball of radius r−1; the notation should be m(G, r−1) or a clarifying remark should be added.
[Section 5, definitions of N^+ and N^-] For vertices at maximum distance from v0 (e.g., |v| = n/2), the definitions of N^+(v) and N^-(v) are not well-defined because there is no layer L_{|v|+1}. The proof should either restrict the statement of Lemma 5.1 to vertices with |v| < n/2 or specify an alternative definition for the antipodal layer.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the proofs rest on independent external lemmas and standard entropy arguments; the gaps noted are correctness issues, not circular reductions.

full rationale

The derivation chain is not circular. Theorem 1.1 is proved from an external packing lemma of Benjamini-Yadin-Yehudayoff (Lemma 3.1) together with a new local counting lemma (Lemma 3.2); neither is defined in terms of the target probability P(R(f) < Mr/2), and the lower bound comes from counting extensions, not from assuming the conclusion. Theorem 1.7 is an entropy argument in the style of Kahn, using Shearer's lemma (Lemma 2.2); the quantity epsilon in Lemma 5.1 is the probability being bounded, not a parameter fitted to the claimed conclusion. The only self-citation, [9] by Krueger, Li, and the second author, appears in the introduction as contextual commentary on an improved expander result and is never used in a proof. There are genuine correctness gaps: the proof of Theorem 1.1 applies Lemma 3.1 with m = max|B_{r-1}| although the lemma's m is max|B_r|, and Lemma 5.1 asserts a vertex-transitive symmetry for a measure pinned at v0. These are unsupported steps in the argument, but they are not cases where a prediction or first-principles result is identical to its own input by construction. Therefore the circularity score is 0.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No numbers are fitted to data; the only constants are universal existence constants. The paper's claims rest on standard external lemmas, namely Shearer's Lemma, the [3] ball lemma, the scaling-limit proposition from [10], and the structural assumption that n is even for the C_{n,k} theorem. No new particles, forces, or entities are postulated.

assumptions (4)

standard math Shearer's Lemma (Lemma 2.2), quoted from Chung-Graham-Frankl-Shearer [5], is applied to a weighted cover of V(C_{n,k}) in the proof of Lemma 5.1.
Used in Section 5 to upper bound H(f); correctness of the lemma and of the cover weights is load-bearing for Theorem 1.7.
standard math Proposition 4.1: as M tends to infinity, a uniform random M-Lipschitz function divided by M converges in distribution to a uniform random real-valued 1-Lipschitz function; quoted from Peled-Samotij-Yehudayoff [10, page 8].
This bridges Theorem 1.1 to Theorem 1.3; the paper does not prove it.
standard math Lemma 3.1 (Claim 2.5 in [3]): for any W, there is a set of at least |W|/m^2 centers with pairwise disjoint exact-radius-r balls, where m is the maximum size of a radius-r ball.
First step of the proof of Theorem 1.1; the proof assumes this supply of disjoint balls.
domain assumption For Theorem 1.7, n is even so C_{n,k} is bipartite and a cycle traversing all layers exists; the odd-n case is asserted in a footnote but not proved.
The entropy/Shearer cover and the derivation of Theorem 1.7 from Lemma 5.1 use the bipartite cycle structure.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Random Lipschitz functions on graphs with weak expansion." pith.science (2026). https://pith.science/paper/5APXCOHA

@misc{pith2026241109640,
  author       = {Pith},
  title        = {Pith review of: Random Lipschitz functions on graphs with weak expansion},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5APXCOHA}},
  note         = {Machine review of arXiv:2411.09640}
}

abstract

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.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

11 extracted references · 9 canonical work pages

[10]

Grounded Lipschitz functions on trees are typically flat.Electronic Communi- cations in Probability, 18:1–9, 2013

Ron Peled, Wojciech Samotij, and Amir Yehudayoff. Grounded Lipschitz functions on trees are typically flat.Electronic Communi- cations in Probability, 18:1–9, 2013. 1, 2, 10

work page 2013
[3]

Random graph-homomorphisms and logarithmic degree

Itai Benjamini, Ariel Yadin, and Amir Yehudayoff. Random graph-homomorphisms and logarithmic degree. Electronic Journal of Probability, 12:926–950, 2007. 1, 3, 4, 6, 7, 10

work page 2007
[1]

On random graph homomorphisms into Z

Itai Benjamini, Olle H ¨aggstr¨om, and Elchanan Mossel. On random graph homomorphisms into Z. Journal of Combinatorial Theory, Series B, 78(1):86–114, 2000. 1, 3, 11

work page 2000
[2]

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

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

work page 1994
[4]

On the local convergence of integer-valued lipschitz functions on regular trees

Nathaniel Butler, Kesav Krishnan, Gourab Ray, and Yinon Spinka. On the local convergence of integer-valued lipschitz functions on regular trees. arXiv preprint arXiv:2410.05542, 2024. 2

arXiv 2024
[5]

Some intersection theorems for ordered sets and graphs

Fan RK Chung, Ronald L Graham, Peter Frankl, and James B Shearer. Some intersection theorems for ordered sets and graphs. Journal of Combinatorial Theory, Series A, 43(1):23–37, 1986. 6

work page 1986
[6]

H-coloring tori

John Engbers and David Galvin. H-coloring tori. Journal of Combinatorial Theory, Series B, 102(5):1110–1133, 2012. 5

work page 2012
[7]

On homomorphisms from the hamming cube to Z

David Galvin. On homomorphisms from the hamming cube to Z. Israel Journal of Mathematics, 138:189–213, 2003. 3

work page 2003

Show all 11 references

[8]

Range of cube-indexed random walk

Jeff Kahn. Range of cube-indexed random walk. Israel Journal of Mathematics, 124:189–201, 2001. 3, 5 16 S. IS ¸IK AND J. PARK

2001
[9]

Lipschitz functions on weak expanders

Robert A Krueger, Lina Li, and Jinyoung Park. Lipschitz functions on weak expanders. arXiv preprint arXiv:2408.14702, 2024. 2

2024 arXiv
[11]

Lipschitz functions on expanders are typically flat

Ron Peled, Wojciech Samotij, and Amir Yehudayoff. Lipschitz functions on expanders are typically flat. Combinatorics, Probability and Computing, 22(4):566–591, 2013. 1, 2, 3 DEPARTMENT OF MATHEMATICS , STANFORD UNIVERSITY Email address: senemi@stanford.edu DEPARTMENT OF MATHEM...

2013

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.

[1] [10]

Grounded Lipschitz functions on trees are typically flat.Electronic Communi- cations in Probability, 18:1–9, 2013

Ron Peled, Wojciech Samotij, and Amir Yehudayoff. Grounded Lipschitz functions on trees are typically flat.Electronic Communi- cations in Probability, 18:1–9, 2013. 1, 2, 10

work page 2013

[2] [3]

Random graph-homomorphisms and logarithmic degree

Itai Benjamini, Ariel Yadin, and Amir Yehudayoff. Random graph-homomorphisms and logarithmic degree. Electronic Journal of Probability, 12:926–950, 2007. 1, 3, 4, 6, 7, 10

work page 2007

[3] [1]

On random graph homomorphisms into Z

Itai Benjamini, Olle H ¨aggstr¨om, and Elchanan Mossel. On random graph homomorphisms into Z. Journal of Combinatorial Theory, Series B, 78(1):86–114, 2000. 1, 3, 11

work page 2000

[4] [2]

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

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

work page 1994

[5] [4]

On the local convergence of integer-valued lipschitz functions on regular trees

Nathaniel Butler, Kesav Krishnan, Gourab Ray, and Yinon Spinka. On the local convergence of integer-valued lipschitz functions on regular trees. arXiv preprint arXiv:2410.05542, 2024. 2

arXiv 2024

[6] [5]

Some intersection theorems for ordered sets and graphs

Fan RK Chung, Ronald L Graham, Peter Frankl, and James B Shearer. Some intersection theorems for ordered sets and graphs. Journal of Combinatorial Theory, Series A, 43(1):23–37, 1986. 6

work page 1986

[7] [6]

H-coloring tori

John Engbers and David Galvin. H-coloring tori. Journal of Combinatorial Theory, Series B, 102(5):1110–1133, 2012. 5

work page 2012

[8] [7]

On homomorphisms from the hamming cube to Z

David Galvin. On homomorphisms from the hamming cube to Z. Israel Journal of Mathematics, 138:189–213, 2003. 3

work page 2003