Juntas in the ${\ell }^1$-grid and Lipschitz maps between discrete tori

Abstract

We show that if $A\subset [k{]}^n$, then $A$ is $\epsilon$-close to a junta depending upon at most $\exp (O(|\partial A|/(k^{n-1}\epsilon )))$ coordinates, where $\partial A$ denotes the edge-boundary of $A$ in the ${\ell }^1$-grid. This is sharp up to the value of the absolute constant in the exponent. This result can be seen as a generalisation of the Junta theorem for the discrete cube, from [E. Friedgut, Boolean functions with low average sensitivity depend on few coordinates, Combinatorica 18 (1998), 27-35], or as a characterization of large subsets of the ${\ell }^1$-grid whose edge-boundary is small. We use it to prove a result on the structure of Lipschitz functions between two discrete tori; this can be seen as a discrete, quantitative analogue of a recent result of Austin [T. Austin, On the failure of concentration for the ${\ell }^{\infty }$-ball, preprint]. We also prove a refined version of our junta theorem, which is sharp in a wider range of cases.

29 pages. A mistake in Example 2 (pointed out by an anonymous referee) has now been corrected

References in corpus (2)

• On the failure of concentration for the \ell_\infty-ball
• Bi-Lipschitz Bijection between the Boolean Cube and the Hamming Ball

Cited by in corpus (1)

• An unified approach to the Junta theorem for discrete and continuous models