Semi-definite method in Combinatorics

本文的目标是利用半定规划和结构化方法系统地研究一类极值组合问题。极值组合学是离散数学中一个重要而活跃的领域，它研究满足一定要求的组合结构的最大尺寸。极值组合学的结果经常与计算机科学、信息论、数论和/或几何学中的问题有关。 极值组合学中的许多结果都是利用归纳法、Cauchy-Schwarz不等式等少数工具，即半定方法得到的。 最近，Razborov开发了一种标志演算，它以纯粹的形式捕获了许多可用的技术，特别是允许一个人计算搜索正确的组合。在过去的几年里，这种方法已经导致了计算机生成的几个经典命题的证明和改进的最佳界限相关的一些人。PI建议继续这条调查路线，将考虑的问题扩展到加法数论和离散几何中的问题。PI还建议将这些计算方法与结构图理论的技术结合联合收割机。 最后，PI建议研究极值组合学中半定方法的局限性。Lovasz和Szegedy观察到极值图论中的一大类有效不等式可以用Cauchy-Schwarz不等式以任意精度近似。哈塔米和PI已经证明，并非所有这样的不等式都直接从柯西-施瓦茨不等式导出。然而，极值组合学中的大型结构化不等式子类仍然可以使用半定方法来证明。

The goal of this proposal is a systematic investigation of a class of problems of in extremal combinatorics using semi-definite programming and structural methods. Extremal combinatorics is an important and active area of discrete mathematics, investigating maximum size of a combinatorial structure satisfying certain requirements. Results in extremal combinatorics are frequently related to problems in computer science, information theory, number theory and/or geometry. Many results in extremal combinatorics are obtained using just a handful of instruments, such as induction and Cauchy-Schwarz inequality, i.e. the semi-definite method. Recently, Razborov developed a flag calculus which captures many of the available techniques in pure form, and allows one, in particular, to computerize the search for the right combination. In the last couple of years, this approach has led to computer-generated proofs of several classical conjectures and improvement of the best bounds related to a number of others. The PI propose to continue this line of investigation, extending the classes of considered questions to problems in additive number theory and discrete geometry. The PI also proposes to combine these computational methods with techniques from structural graph theory. Finally, the PI proposes to investigate the limitations of the semi-definite method in extremal combinatorics. Lovasz and Szegedy have observed that a large class of valid inequalities in extremal graph theory can be approximated with arbitrary precision by Cauchy-Schwarz inequalities. Hatami and the PI have shown that not all such inequalities follow directly from the Cauchy-Schwarz ones. It is still, however, possible that large structured subclasses of inequalities in extremal combinatorics can be proved using the semi-definite method.