Juntas in the ℓ1‐grid and Lipschitz maps between discrete tori1. Issue 2 (14th November 2015) - Benjamini, Itai; Ellis, David; Friedgut, Ehud; Keller, Nathan; Sen, Arnab
Abstract: We show that if A ⊂ [ k ] n, then A is ϵ ‐close to a junta depending upon at most exp ( O ( | ∂ A | / ( k n − 1 ϵ ) ) ) coordinates, where ∂ A denotes the edge‐boundary of A in the ℓ 1 ‐grid. This bound 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 [6], or as a characterisation of large subsets of the ℓ 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 [1]. We also prove a refined version of our junta theorem, which is sharp in a wider range of cases. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 49, 253–279, 2016