Revised: February 20, 2024
Published: May 26, 2025
Abstract: [Plain Text Version]
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.
Licensed under a Creative Commons Attribution License (CC-BY)