Juntas in the ℓ1-grid and Lipschitz maps between discrete tori

Itai Benjamini, David Ellis, Ehud Friedgut, Nathan Keller, Arnab Sen

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

We show that if A ⊂ [k]n, then A is ε -close to a junta depending upon at most exp(O(|∂A|/(kn-1ε))) coordinates, where ∂A denotes the edge-boundary of A in the l1 -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 l1 -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.

Original languageEnglish (US)
Pages (from-to)253-279
Number of pages27
JournalRandom Structures and Algorithms
Volume49
Issue number2
DOIs
StatePublished - Sep 1 2016

Bibliographical note

Publisher Copyright:
© 2015 Wiley Periodicals, Inc.

Keywords

  • Boolean functions
  • Lipschitz
  • influence

Fingerprint

Dive into the research topics of 'Juntas in the ℓ<sub>1</sub>-grid and Lipschitz maps between discrete tori'. Together they form a unique fingerprint.

Cite this