Lipschitz functions on weak expanders
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910578128191488 |
|---|---|
| author | Krueger, Robert A. Li, Lina Park, Jinyoung |
| author_facet | Krueger, Robert A. Li, Lina Park, Jinyoung |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_14702 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Lipschitz functions on weak expanders Krueger, Robert A. Li, Lina Park, Jinyoung Probability Combinatorics 60C05, 05C48 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. |
| title | Lipschitz functions on weak expanders |
| topic | Probability Combinatorics 60C05, 05C48 |
| url | https://arxiv.org/abs/2408.14702 |