{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,6]],"date-time":"2026-07-06T20:04:48Z","timestamp":1783368288877,"version":"3.54.6"},"reference-count":13,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2013,6,11]],"date-time":"2013-06-11T00:00:00Z","timestamp":1370908800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2013,7]]},"abstract":"<jats:p>This work studies the typical behaviour of random integer-valued Lipschitz functions on expander graphs with sufficiently good expansion. We consider two families of functions: <jats:italic>M<\/jats:italic>-Lipschitz functions (functions which change by at most <jats:italic>M<\/jats:italic> along edges) and integer-homomorphisms (functions which change by exactly 1 along edges). We prove that such functions typically exhibit very small fluctuations. For instance, we show that a uniformly chosen <jats:italic>M<\/jats:italic>-Lipschitz function takes only <jats:italic>M<\/jats:italic>+1 values on most of the graph, with a double exponential decay for the probability of taking other values.<\/jats:p>","DOI":"10.1017\/s0963548313000163","type":"journal-article","created":{"date-parts":[[2013,6,11]],"date-time":"2013-06-11T09:33:45Z","timestamp":1370943225000},"page":"566-591","source":"Crossref","is-referenced-by-count":14,"title":["Lipschitz Functions on Expanders are Typically Flat"],"prefix":"10.1017","volume":"22","author":[{"given":"RON","family":"PELED","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"WOJCIECH","family":"SAMOTIJ","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"AMIR","family":"YEHUDAYOFF","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2013,6,11]]},"reference":[{"key":"S0963548313000163_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/BF02772616"},{"key":"S0963548313000163_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2011.12.004"},{"key":"S0963548313000163_ref8","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-06-01126-8"},{"key":"S0963548313000163_ref11","unstructured":"Peled R. (2010) High-dimensional Lipschitz functions are typically flat. arXiv:1005.4636"},{"key":"S0963548313000163_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2012.05.003"},{"key":"S0963548313000163_ref9","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548301004631"},{"key":"S0963548313000163_ref3","doi-asserted-by":"publisher","DOI":"10.1214\/EJP.v12-427"},{"key":"S0963548313000163_ref12","unstructured":"Peled R. , Samotij W. and Yehudayoff A. Grounded Lipschitz functions on trees are typically flat. Submitted."},{"key":"S0963548313000163_ref7","doi-asserted-by":"publisher","DOI":"10.1007\/BF02783426"},{"key":"S0963548313000163_ref1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1999.1931"},{"key":"S0963548313000163_ref2","doi-asserted-by":"publisher","DOI":"10.1002\/1098-2418(200008)17:1<20::AID-RSA2>3.0.CO;2-S"},{"key":"S0963548313000163_ref13","unstructured":"Peled R. , Samotij W. and Yehudayoff A. H-coloring expander graphs. In preparation."},{"key":"S0963548313000163_ref6","volume-title":"Mem. Amer. Math. Soc.","author":"Friedman","year":"2008"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548313000163","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,23]],"date-time":"2019-04-23T21:15:12Z","timestamp":1556054112000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548313000163\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,6,11]]},"references-count":13,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,7]]}},"alternative-id":["S0963548313000163"],"URL":"https:\/\/doi.org\/10.1017\/s0963548313000163","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,6,11]]}}}