We show equivalences between several high-dimensional problems in extremal combinatorics and parallel repetition of multiplayer (multiprover) games over large answer alphabets. This extends the forbidden-subgraph technique, previously studied by Verbitsky (Theoretical Computer Science 1996), Feige and Verbitsy (Combinatorica 2002), and H\k{a}z{\l}a , Holenstein and Rao (2016), to all $k$-player games, and establishes new connections to problems in combinatorics. We believe that these connections may help future progress in both fields.
翻译：我们证明了极值组合学中的若干高维问题与基于大答案字母表的多人（多证明者）博弈的并行重复之间的等价关系。这一结论将先前由Verbitsky（理论计算机科学 1996）、Feige与Verbitsy（组合学杂志 2002）以及H\k{a}z{\l}a、Holenstein和Rao（2016）研究的禁止子图技术，推广至所有$k$人博弈，并建立了与组合学问题的新联系。我们相信这些关联可能有助于推动两个领域的未来发展。
相关内容
微信扫码咨询专知VIP会员