{"id":"564de0a9-163e-4c6d-9bad-1d025686bb8f","arxiv_id":"2411.09640","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Random M-Lipschitz functions on graphs with slowly growing balls have range at least about M r/2, while on layered cycles C_{n,k} with k above γ M^2 log(Mn) the range is exactly M+1 with high probability.","lead":"Random functions with bounded local slopes on a graph usually have a large total range once all small-radius balls in the graph are small. The paper also finds a sharp window on layered cycle graphs where such random functions have the smallest possible range instead.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Unsupported 'symmetry' in Lemma 5.1: the pinned measure is not vertex-transitive, so a single failure probability ε cannot serve both the entropy bound and the cycle union bound.","rationale":"The Reader's weakest_assumption identifies a genuine but localized flaw: the proof of Theorem 1.1 conflates max|B_{r-1}| with the parameter m in Lemma 3.1, which is max|B_r|. This is a clear equivocation, and for r=1 Lemma 3.1 can deliver zero disjoint balls. However, for r≥2 the hypothesis bounds the maximum degree, so max|B_r| ≤ (c log n)^r and the proof is repairable by tracking the two maxima separately; the main applications use r ≥ 2. The more serious issue lies in Theorem 1.7. The proof of Lemma 5.1 depends on a single parameter ε that is simultaneously treated as a vertex-independent failure probability and as the average appearing in the entropy inequality. The claimed vertex independence is based on an invalid symmetry: the measure on Lip_v0 fixes v0, so the stabilizer of v0 does not act transitively on layers at different distances. Consequently, the union bound over the spanning cycle needs the maximum of the per-vertex failure probabilities, while the entropy argument can only give information about their average unless the vertex probabilities are equal, which is not established and is false in simple pinned models. This gap affects the entire proof of Theorem 1.7, not a corner case. A repair seems plausible by replacing the single ε with layer-dependent probabilities and using that the cycle visits one vertex per layer, so the union bound only requires the average; but as written the proof is incomplete. The reader's verdict of CONDITIONAL remains appropriate, so I do not change it, but my diagnosis of the most load-bearing weakness differs.","tokens_in":15733,"tokens_out":44579,"duration_ms":397848,"concrete_test":"For C_{6,2} with M=2, enumerate all functions in Lip_v0(C_{6,2};M) (there are finitely many, about (2M+1)^{N-1} upper bounded) and compute p_i for layers L0, L1, L2, L3. If the p_i differ, the symmetry claim in (22) is false. Then check whether replacing ε in (27) by the maximum p_i still yields the claimed O(1/(γ n)) bound; if not, the proof needs an averaging argument or a different union bound.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 5.1 defines ε in (22) as P(|f̄_{N_v^+}| ≠ M+1) and asserts that, by symmetry of C_{n,k}, this probability is equal for every vertex. This assertion is not justified: the uniform measure on Lip_v0(C_{n,k};M) fixes v0=0, so it is invariant only under automorphisms stabilizing v0. The stabilizer of v0 in C_{n,k} acts on layers by the reflection i ↦ −i and arbitrary permutations within each layer; it does not act transitively on vertices at different distances from v0. Thus P(|f̄_{N_v^+}| ≠ M+1) can depend on |v|, as in the analogous one-dimensional pinned Lipschitz model where boundary layers have different fluctuation statistics. The proof then uses this single ε in two incompatible ways. In (21) and the cycle union bound, it needs ε to be a per-vertex probability (indeed the maximum over vertices on the spanning cycle), because P(C ideal) ≥ 1 − 4nε requires the same ε for every edge endpoint. In the entropy upper bound leading to (27), the term (N/2)[(1−ε)log(M+1)^2 + ε log M(M+2)] is obtained by replacing the per-vertex probabilities P(f̄_{N_v} = (c,c′)) with a single ε; this is algebraically valid only if ε is the average of those probabilities over all even vertices, since the displayed expression is linear in ε. If the p_v are not constant, the entropy argument controls an average while the union bound needs a maximum, and no separate argument bridges this gap. The r=1 parameter mismatch in Theorem 1.1 noted by the Reader is a real but localized issue; the ε equivocation affects the entire proof of Theorem 1.7, the paper's other main result, and is therefore the more load-bearing concern.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":16036,"tokens_out":20520,"duration_ms":174868,"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":[{"comment":"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":"Section 3.2, proof of Theorem 1.1"},{"comment":"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.","section":"Section 5, Lemma 5.1 and derivation of Theorem 1.7"}],"minor_comments":[{"comment":"There is a typo in the introduction: 'ths result there was recently improved' should read 'the result there was recently improved'.","section":"Abstract and Introduction"},{"comment":"The notation 'on(1)' is nonstandard; it should be typeset as 'o_n(1)' to match the definition given in the introduction.","section":"Throughout"},{"comment":"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":"Lemma 3.2"},{"comment":"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.","section":"Section 5, definitions of N^+ and N^-"}],"recommendation":"major_revision","confidential_remarks":"Both gaps are substantive but potentially fixable. The Theorem 1.1 gap may be repaired by strengthening the hypothesis to control balls of radius r, or by a separate argument when B_r is much larger than B_{r-1}; this is a localized patch. The Section 5 symmetry issue is more serious: the entropy method and the union bound genuinely require different averaging regimes, and bridging them may require a new idea rather than a simple correction. I would send the paper back for major revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nNow 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.\n\nOne 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.\n\nBottom 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.","headline":"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.","tokens_in":16693,"tokens_out":14671,"would_cite":true,"duration_ms":126843,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60C05","05C80","05C12"],"pacs":[],"model":"deepseek-v4-flash","headline":"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$.","keywords":["random Lipschitz functions","weak expansion","range","entropy method","Z-homomorphisms","C_{n,k} layered graph","logarithmic degree","graph homomorphisms"],"falsifier":"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.","tokens_in":15464,"feed_emoji":"📈","tokens_out":22687,"duration_ms":186356,"temperature":0.7,"pith_summary":"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.","feed_headline":"Weak expansion forces random Lipschitz functions to fluctuate","feed_subtitle":"On graphs whose balls stay logarithmic, a uniform M-Lipschitz function typically spans at least M r/2.","key_machinery":"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.","core_discovery":"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$.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the disjoint-ball lemma (Lemma 3.1) and the overall proof strategy that Theorem 1.1 extends.","marker":"[3]"},{"why":"Provides the upper bound on expanders that the new lower bound complements, along with the definition of the spectral-expansion condition.","marker":"[11]"},{"why":"Provides the entropy argument for cube-indexed random walks that Theorem 1.7 adapts to show flatness.","marker":"[8]"},{"why":"Gives the convergence of scaled $M$-Lipschitz measures to the real-valued model used in Theorem 1.3.","marker":"[10]"},{"why":"Supplies the weighted entropy inequality (Lemma 2.2) used in the upper bound for $C_{n,k}$.","marker":"[5]"},{"why":"The multicolor extension of the cube entropy argument that cannot be applied directly because the number of colors grows, motivating the new layer-ordering approach.","marker":"[6]"}],"fun_headline_variants":["Weak expansion forces random Lipschitz functions to fluctuate widely","On weak expanders, random Lipschitz functions span large ranges","Weak expansion guarantees large ranges for random Lipschitz maps","Random M-Lipschitz functions show sharp range transition","Random Lipschitz functions on weak expanders span at least M r/2"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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$.","fun_headline_variants_meta":{"raw":{"variants":["Weak expansion forces random Lipschitz functions to fluctuate widely","On weak expanders, random Lipschitz functions span large ranges","Weak expansion guarantees large ranges for random Lipschitz maps","Random M-Lipschitz functions show sharp range transition","Random Lipschitz functions on weak expanders span at least M r/2"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.002172,"raw_usage":{"total_tokens":8391,"prompt_tokens":892,"completion_tokens":7499,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":508,"completion_tokens_details":{"reasoning_tokens":7411}},"tokens_in":508,"tokens_out":7499,"duration_ms":49019,"temperature":1.0,"reasoning_tokens":7411,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T20:29:33.095665+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Random graph-homomorphisms and logarithmic degree","cited_arxiv_id":null,"evidence_quote":"Supplies the disjoint-ball lemma (Lemma 3.1) and the overall proof strategy that Theorem 1.1 extends."},{"cited_title":"Lipschitz functions on expanders are typically flat","cited_arxiv_id":null,"evidence_quote":"Provides the upper bound on expanders that the new lower bound complements, along with the definition of the spectral-expansion condition."},{"cited_title":"Range of cube-indexed random walk","cited_arxiv_id":null,"evidence_quote":"Provides the entropy argument for cube-indexed random walks that Theorem 1.7 adapts to show flatness."},{"cited_title":"Grounded Lipschitz functions on trees are typically flat.Electronic Communi- cations in Probability, 18:1–9, 2013","cited_arxiv_id":null,"evidence_quote":"Gives the convergence of scaled $M$-Lipschitz measures to the real-valued model used in Theorem 1.3."},{"cited_title":"Some intersection theorems for ordered sets and graphs","cited_arxiv_id":null,"evidence_quote":"Supplies the weighted entropy inequality (Lemma 2.2) used in the upper bound for $C_{n,k}$."},{"cited_title":"H-coloring tori","cited_arxiv_id":null,"evidence_quote":"The multicolor extension of the cube entropy argument that cannot be applied directly because the number of colors grows, motivating the new layer-ordering approach."}],"review_version":1}