Lipschitz Functions on Expanders are Typically Flat

DOI10.1017/S0963548313000163zbMath1274.60029arXiv1203.3930OpenAlexW2962897224MaRDI QIDQ2841490

Wojciech Samotij, Ron Peled, Amir Yehudayoff

Publication date: 26 July 2013

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1203.3930

zbMATH Keywords

bipartite graphsLipschitz functionsexpander graphs

Mathematics Subject Classification ID

Combinatorial probability (60C05) Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics (82B41) Coloring of graphs and hypergraphs (05C15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

Rigidity of 3-colorings of the discrete torus ⋮ Uniform Lipschitz functions on the triangular lattice have logarithmic variations ⋮ Homomorphisms from the torus ⋮ Strongly correlated random interacting processes. Abstracts from the workshop held January 28 -- February 3, 2018 ⋮ Delocalization of uniform graph homomorphisms from \({\mathbb{Z}}^2\) to \({\mathbb{Z}} \) ⋮ Delocalization of two-dimensional random surfaces with hard-core constraints

Cites Work

• Unnamed Item
• \(H\)-colouring bipartite graphs
• \(H\)-coloring tori
• On homomorphisms from the Hamming cube to \(\mathbb{Z}\)
• On random graph homomorphisms into \({\mathbb{Z}}\)
• Random graph-homomorphisms and logarithmic degree
• Expander graphs and their applications
• Range of cube-indexed random walk