Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

McGill University

$26,000.00

Semi-definite method in Combinatorics

FY 2012-13

Summary
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.
Program
Discovery Grants Program - Individual
Location
Quebec, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
418520-2012
Name nom
Norin, Sergey
Department département
Mathematics and Statistics
Organization id
61
Institution établissement
McGill University
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2012
Competition year année de concours
2012
Award amount
26000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1508
Committee name en
Mathematics and Statistics
Committee name fr
Mathématiques et statistique
Area of application code
1200
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Advancement of knowledge
Area of application fr
Avancement des connaissances
Research subject code
2914
Research subject group en
Pure mathematics
Research subject group fr
Mathématiques pures
Research subject en
Combinatorics
Research subject fr
Combinatoire
Partie
1
Nb partie
5
Application title
Semi-definite method in Combinatorics
Keyword
NSERC
Application summary
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.