Semi-definite method in Combinatorics

组合学中的半定法

• 批准号: 418520-2012
• 负责人: Norin, Sergey
• 金额: $ 1.89万
• 依托单位: McGill University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=573702
• 关键词: Semi; definite; method; Combinatorics

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.

本文的目标是用半定规划和结构方法系统地研究一类极值组合问题。极值组合是离散数学中一个重要而活跃的领域，它研究满足一定要求的组合结构的最大尺寸。极值组合的结果经常与计算机科学、信息论、数论和/或几何中的问题有关。