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].
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].
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].
