### Revision(s):

__
Revision #2 to TR18-006 | 19th May 2018 14:13
__
#### Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion

**Abstract:**
We prove that pseudorandom sets in Grassmann graph have near-perfect expansion as hypothesized in [DKKMS-2]. This completes

the proof of the $2$-to-$2$ Games Conjecture (albeit with imperfect completeness) as proposed in [KMS, DKKMS-1], along with a

contribution from [BKT].

The Grassmann graph $Gr_{global}$ contains induced subgraphs $Gr_{local}$ that are themselves isomorphic to Grassmann graphs of lower orders.

A set is called pseudorandom if its density is $o(1)$ inside all subgraphs $Gr_{local}$ whose order is $O(1)$ lower than that of $Gr_{global}$.

We prove that pseudorandom sets have expansion $1-o(1)$, greatly extending the results and techniques in [DKKMS-2].

__
Revision #1 to TR18-006 | 12th January 2018 02:46
__
#### Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion

**Abstract:**
We prove that pseudorandom sets in Grassmann graph have near-perfect expansion as hypothesized in [DKKMS-2]. This completes the proof of the $2$-to-$2$ Games Conjecture (albeit with imperfect completeness) as proposed in [KMS, DKKMS-1], along with a contribution from [BKT, KMMS].

The Grassmann graph $Gr_{global}$ contains induced subgraphs $Gr_{local}$ that are themselves isomorphic to Grassmann graphs of lower orders.

A set is called pseudorandom if its density is $o(1)$ inside all subgraphs $Gr_{local}$ whose order is $O(1)$ lower than that of $Gr_{global}$. We prove that pseudorandom sets have expansion $1-o(1)$, greatly extending the results and techniques in [DKKMS-2].

### Paper:

__
TR18-006 | 10th January 2018 01:42
__

#### Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion

**Abstract:**
We prove that pseudorandom sets in Grassmann graph have near-perfect expansion as hypothesized in [DKKMS-2]. This completes

the proof of the $2$-to-$2$ Games Conjecture (albeit with imperfect completeness) as proposed in [KMS, DKKMS-1], along with a

contribution from [BKT].

The Grassmann graph $Gr_{global}$ contains induced subgraphs $Gr_{local}$ that are themselves isomorphic to Grassmann graphs of lower orders.

A set is called pseudorandom if its density is $o(1)$ inside all subgraphs $Gr_{local}$ whose order is $O(1)$ lower than that of $Gr_{global}$.

We prove that pseudorandom sets have expansion $1-o(1)$, greatly extending the results and techniques in [DKKMS-2].