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 Grglobal contains induced subgraphs Grlocal that are themselves isomorphic to Grassmann graphs of lower orders.
A set is called pseudorandom if its density is o(1) inside all subgraphs Grlocal whose order is O(1) lower than that of Grglobal.
We prove that pseudorandom sets have expansion 1−o(1), greatly extending the results and techniques in [DKKMS-2].
Make this part of your paper trail
Save this paper to a shelf, write a review, and keep your own notes.