Pseudorandom sets in Grassmann graph have near-perfect expansion

• 成果类型: Article
• 署名作者: Khot, Subhash; Minzer, Dor; Safra, Muli
• 刊物名称: ANNALS OF MATHEMATICS
• ISSN/ISSBN: 0003-486X
• DOI: 10.4007/annals.2023.198.1.1
• 发表日期: 2023
• 页码: 1-92
• 关键词: hardness; Inapproximability; proofs; games; APPROXIMATE

摘要

We prove that pseudorandom sets in Grassmann graph have near-perfect expansion. This completes the proof of the 2-to-2 Games Conjecture (albeit with imperfect completeness). Some implications of this new result are improved hardness results for Minimum Vertex Cover, improving on the work of Dinur and Safra [Ann. of Math. 162 (2005), 439-485], and new hardness gaps for Unique-Games. The Grassmann graph Grglobal 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 of a previous work of the authors with Dinur and Kindler.