Repository logo
 

Subsets of Cayley Graphs That Induce Many Edges

Published version
Peer-reviewed

Type

Article

Change log

Authors

Gowers, Timothy 
Janzer, Oliver 

Abstract

Let G be a regular graph of degree d and let AV(G). Say that A is η-closed if the average degree of the subgraph induced by A is at least ηd. This says that if we choose a random vertex xA and a random neighbour y of x, then the probability that yA is at least η. The work of this paper was motivated by an attempt to obtain a qualitative description of closed subsets of the Cayley graph Γ whose vertex set is F2n1⊗⋯⊗F2nd with two vertices joined by an edge if their difference is of the form u1⊗⋯⊗ud. 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 η-closed sets in Cayley graphs on arbitrary finite Abelian groups that implies the conjecture and can be considered as a "highly asymmetric Balog-Szemer'edi-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 Γ.

Description

Keywords

Unique Games Conjecture, tensors, Cayley graphs

Journal Title

THEORY OF COMPUTING

Conference Name

Journal ISSN

1557-2862
1557-2862

Volume Title

15

Publisher

Theory of Computing Exchange