Theory of Computing
-------------------
Title : Subsets of Cayley Graphs that Induce Many Edges
Authors : Timothy Gowers and Oliver Janzer
Volume : 15
Number : 20
Pages : 1-29
URL : https://theoryofcomputing.org/articles/v015a020
Abstract
--------
Let $G$ be a regular graph of degree $d$ and let $A\subset V(G)$. Say
that $A$ is _$\eta$-closed_ if the average degree of the subgraph
induced by $A$ is at least $\eta d$. This says that if we choose a
random vertex $x\in A$ and a random neighbour $y$ of $x$, then the
probability that $y\in A$ is at least $\eta$. This paper was motivated
by an attempt to obtain a qualitative description of closed subsets of
the Cayley graph $\Gamma$ whose vertex set is
$\mathbb{F}_2^{n_1}\otimes \dots \otimes \mathbb{F}_2^{n_d}$ with two
vertices joined by an edge if their difference is of the form
$u_1\otimes \cdots \otimes u_d$. For the matrix case (that is, when
$d=2$), such a description was obtained by Khot, Minzer and Safra, a
breakthrough that completed the proof of the 2-to-2 conjecture. In
this paper, we formulate a conjecture for higher dimensions, and prove
it in an important special case. Also, we identify a statement about
$\eta$-closed sets in Cayley graphs on arbitrary finite Abelian groups
that implies the conjecture and can be considered as a "highly
asymmetric Balog--Szemeredi--Gowers theorem" when it holds. We
conclude the paper by showing that this statement is not true for an
arbitrary Cayley graph. It remains to decide whether the statement can
be proved for the Cayley graph $\Gamma$.