REVIEW 4 cited by
Lipschitz functions on weak expanders
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Lipschitz functions on weak expanders
abstract
Given a connected finite graph $G$, an integer-valued function $f$ on $V(G)$ is called $M$-Lipschitz if the value of $f$ changes by at most $M$ along the edges of $G$. In 2013, Peled, Samotij, and Yehudayoff showed that random $M$-Lipschitz functions on graphs with sufficiently good expansion typically exhibit small fluctuations, giving sharp bounds on the typical range of such functions, assuming $M$ is not too large. We prove that the same conclusion holds under a relaxed expansion condition and for larger $M$, (partially) answering questions of Peled et al. Our techniques involve a combination of Sapozhenko's graph container methods and entropy methods from information theory.
Forward citations
Cited by 4 Pith papers
-
Range of random $\mathbb Z$-homomorphisms on weak expanders
Random Z-homomorphisms on weak expanders are O(log log n)-flat with high probability, answering a question of Peled-Samotij-Yehudayoff, and at most 5-valued on Hamming-cube middle layers.
-
Random homomorphisms and Lipschitz functions on trees
Random homomorphisms on general finite trees have root values stochastically comparable to discrete Gaussians with sub-Gaussian tails and constant-factor variance bounds controlled solely by effective resistance, exte...
-
Lipschitz Functions on Sparse Graphs II
Proves log c(G(n,d/n)) = π²/(6d) + o(d^{-1}) whp and gives matching lower plus weaker upper bound for log c(Q_d) on the hypercube.
-
Entropy methods in combinatorics
A selective survey of entropy methods in combinatorics, detailing randomized chain rules, Shearer's inequality, random homomorphisms, Pinsker-type arguments, the union-closed sets breakthrough, and entropy approaches ...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.