Theory of Computing
-------------------
Title     : Small Set Expansion in the Johnson Graph
Authors   : Subhash Khot, Dor Minzer, Dana Moshkovitz, and Muli Safra
Volume    : 21
Number    : 2
Pages     : 1-43
URL       : https://theoryofcomputing.org/articles/v021a002

Abstract
--------

An $n$-vertex graph is called a _small-set expander_ if any set of
size $o(n)$ contains at most a $o(1)$ fraction of the edges that touch
it. The goal of this paper is to investigate small-set expansion
properties of the Johnson graph, which is not a small-set expander.

We obtain a qualitative descriptions of all small sets that violate
the small-set expansion property in the Johnson graph: we show that
any such set is correlated with some union of small intersections of
"basic sets," where each basic set is a dictatorship--i.e., belonging
to it depends only on containing a single coordinate $i$. This
condition is necessary and sufficient, since any such set violates the
small-set expansion property.

The statement and its proof are inspired by recent analogous questions
on the Grassmann graph (Dinur et al., _STOC'18_ and _Israel J. Math.,
2021_) and their application to the $2$-to-$1$ Games Conjecture. To
prove our results, we build on and extend the techniques of Dinur et
al., _Israel J. Math., 2021_. Subsequently to our work, the full
expansion hypothesis for the Grassmann graph was proved in Khot et
al., _Ann. Math. 2023._