Semi-definite method in Combinatorics

本文的目的是利用半定规划和结构方法对极值组合数学中的一类问题进行系统的研究。极值组合学是离散数学的一个重要而活跃的领域，研究满足一定条件的组合结构的最大尺寸。极值组合数学的结果通常与计算机科学、信息论、数论和/或几何中的问题有关。 极值组合数学中的许多结果都是用归纳法、柯西-施瓦茨不等式等工具，即半定方法得到的。最近，拉兹博罗夫开发了一种旗帜演算，它以纯形式捕获了许多可用的技术，特别是允许一个人通过计算机来搜索正确的组合。在过去的几年里，这种方法已经导致了几个经典猜想的计算机生成证明，以及与其他一些猜想相关的最佳界的改进。PI建议继续这一调查，将所考虑的问题的类别扩展到加法数论和离散几何中的问题。PI还建议将这些计算方法与结构图论中的技术相结合。 最后，PI建议研究极值组合数学中半定方法的局限性。Lovasz和Szegedy已经观察到极值图论中的一大类有效的不等式可以用Cauchy-Schwarz不等式以任意精度逼近。Hatami和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.