Grant: Discovery Grants Program - Individual
McGill University
$18,000.00
Theory of graph homomorphisms and extremal combinatorics
FY 2015-16
Summary
Discrete mathematics or combinatorics is a fundamental mathematical discipline
which focuses on the study of discrete objects and their properties. This area which is as old as
the human ability to count, has attracted many strong mathematicians and is experiencing tremendous growth during the last fifty years. One of the main reasons for this is its intimate connection with computer science, the utility of which is obvious. Moreover combinatorics has applications to probability, set theory, cryptography, communication theory, the geometry of Banach spaces, harmonic analysis, number theory, ... the list goes on and on.
However, still many of these applications would fail to impress many mathematicians who regard combinatorics as a large collection of isolated results and problems that can be disregarded as technical part of mathematics. This I believe is mainly due to the fact there has not been much theory developed to connect these results and problems to each other. However, in the last decade, this has started to change, and this change has gained more speed recently.
A significant part of modern extremal combinatorics is dedicated to the study of the asymptotic relations between subgraph densities. These relations are usually expressed as algebraic inequalities between subgraph densities. Despite the variety of ingenious and hard results in asymptotic graph theory, surprisingly, there seem to exist only a handful of essentially different techniques in this area, and many known results are proven by clever combinations these techniques and tools.
In recent years a new line of researches in the direction of developing theories that explains these similarities in the proofs of various seemingly very different results in this area has emerged. The purpose of this line of research is to develops a general theory that (1) reveals the general nature of this area of mathematics (2) encompasses the main techniques used in this area and provides methods for applying them in an automated manner (3) provides new tools for solving the large collection of open problems in this area.
The problems that I am working on are the general problems that reveal the limitations and powers of these theories. These problems if solved will increase our general understanding of the nature of the area of extremal combinatorics.
An important result in this area says that many theorems follow from the positive semi-definiteness of a certain infinite matrix. This positive semi-definite characterization is a powerful approach for proving such inequalities. This method is very convenient to program, so that the search for ``right'' relations can be to a large degree computerized. In other words, in this area certain type of problems which were previously solved by tedious work of important mathematics can now be solved by a computer problems.
I have already used this method to solve an open problem, and in the future I am planning to combine this method with other auxiliary tools and techniques to attack to various open problems in extremal graph theory.
Program
Discovery Grants Program - Individual
Recipient
Location
Quebec, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
408045-2011
Name nom
Hatami, Hamed
Department département
Computer Science, School of
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
2015
Competition year année de concours
2011
Award amount
18000
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
5
Nb partie
5
Application title
Theory of graph homomorphisms and extremal combinatorics
Keyword
NSERC
Application summary
Discrete mathematics or combinatorics is a fundamental mathematical discipline
which focuses on the study of discrete objects and their properties. This area which is as old as
the human ability to count, has attracted many strong mathematicians and is experiencing tremendous growth during the last fifty years. One of the main reasons for this is its intimate connection with computer science, the utility of which is obvious. Moreover combinatorics has applications to probability, set theory, cryptography, communication theory, the geometry of Banach spaces, harmonic analysis, number theory, ... the list goes on and on.
However, still many of these applications would fail to impress many mathematicians who regard combinatorics as a large collection of isolated results and problems that can be disregarded as technical part of mathematics. This I believe is mainly due to the fact there has not been much theory developed to connect these results and problems to each other. However, in the last decade, this has started to change, and this change has gained more speed recently.
A significant part of modern extremal combinatorics is dedicated to the study of the asymptotic relations between subgraph densities. These relations are usually expressed as algebraic inequalities between subgraph densities. Despite the variety of ingenious and hard results in asymptotic graph theory, surprisingly, there seem to exist only a handful of essentially different techniques in this area, and many known results are proven by clever combinations these techniques and tools.
In recent years a new line of researches in the direction of developing theories that explains these similarities in the proofs of various seemingly very different results in this area has emerged. The purpose of this line of research is to develops a general theory that (1) reveals the general nature of this area of mathematics (2) encompasses the main techniques used in this area and provides methods for applying them in an automated manner (3) provides new tools for solving the large collection of open problems in this area.
The problems that I am working on are the general problems that reveal the limitations and powers of these theories. These problems if solved will increase our general understanding of the nature of the area of extremal combinatorics.
An important result in this area says that many theorems follow from the positive semi-definiteness of a certain infinite matrix. This positive semi-definite characterization is a powerful approach for proving such inequalities. This method is very convenient to program, so that the search for ``right'' relations can be to a large degree computerized. In other words, in this area certain type of problems which were previously solved by tedious work of important mathematics can now be solved by a computer problems.
I have already used this method to solve an open problem, and in the future I am planning to combine this method with other auxiliary tools and techniques to attack to various open problems in extremal graph theory.