Grant: Discovery Grants Program - Individual
Carleton University
$14,000.00
Analytic and Probabilistic Combinatorics, and Long Cycles in Graphs
FY 2018-19
Summary
With the explosion of data in our information age,*we need to deal with discrete structures of ever-growing size. Analytic and probabilistic combinatorics is a branch of discrete mathematics which uses tools from analysis and probability theory to study the properties of large discrete structures. Also graphs serve as very useful models for many discrete structures arising from applications. In this proposal I address some specific problems in analytic and probabilistic combinatorics, and graph theory.*Many combinatorial structures are composed of supports and parts. Runs in words and cycles in permutations are two well-known examples. One of the problems in my proposal deals with the distribution of some random variables associated with part sizes such as the maximum part size, the number of distinct part sizes, and the number of parts of a given size.*The problem of studying the size of the union of random subsets arises from many applications such as statistical sampling and polynomials over a finite field. I would like to study the distribution of the size of the union of subsets chosen from a given set according to some distributions.*Surface maps appear naturally in many applications. For example fullerenes (planar cubic maps such that each face is either a pentagon or a hexagon) have been studied extensively by chemists, and surface maps have been studied extensively by quantum physicists. I would like to count fullerenes and also explore relations between surface maps and binary trees.*Skylines have emerged as a useful notion in database queries for selecting representative groups in multivariate data samples. Roughly speaking, a point p in a data set is called a skyline if there is no point in the data set which ""dominates"" p. One of the problems addressed in my proposal is about estimating the expected number of skylines in n random points from a given d-dimensional set and studying the phase transition as d increases.*Due to the rapid expansion of the casino industry (including lotteries and online gaming), games of chance are now almost everywhere. One of the problems addressed in my proposal analyzes Hold'em Poker. Combinatorial, probabilistic, and game theoretical analyses are required to find the optimal (near-optimal) strategies. This has also become a hot topic in artificial intelligence.*Finding long cycles in a graph is a fundamental problem in graph theory and it also has many applications. The circumference of a graph G, denoted by c(G), is the length of a longest cycle in G. There are two long standing open problems about the best possible lower bound for c(G), one for 3-connected graphs with maximum degree at least 4, and the other for 3-connected cubic graphs. The current published bounds are still far away from the best possible bounds. I would like to obtain better bounds for both problems.*
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2015-04010
Name nom
Gao, Zhicheng
Department département
Mathematics and Statistics, School of
Organization id
23
Institution établissement
Carleton University
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2018
Competition year année de concours
2015
Award amount
14000
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
4
Nb partie
5
Application title
Analytic and Probabilistic Combinatorics, and Long Cycles in Graphs
Keyword
NSERC
Application summary
With the explosion of data in our information age,*we need to deal with discrete structures of ever-growing size. Analytic and probabilistic combinatorics is a branch of discrete mathematics which uses tools from analysis and probability theory to study the properties of large discrete structures. Also graphs serve as very useful models for many discrete structures arising from applications. In this proposal I address some specific problems in analytic and probabilistic combinatorics, and graph theory.*Many combinatorial structures are composed of supports and parts. Runs in words and cycles in permutations are two well-known examples. One of the problems in my proposal deals with the distribution of some random variables associated with part sizes such as the maximum part size, the number of distinct part sizes, and the number of parts of a given size.*The problem of studying the size of the union of random subsets arises from many applications such as statistical sampling and polynomials over a finite field. I would like to study the distribution of the size of the union of subsets chosen from a given set according to some distributions.*Surface maps appear naturally in many applications. For example fullerenes (planar cubic maps such that each face is either a pentagon or a hexagon) have been studied extensively by chemists, and surface maps have been studied extensively by quantum physicists. I would like to count fullerenes and also explore relations between surface maps and binary trees.*Skylines have emerged as a useful notion in database queries for selecting representative groups in multivariate data samples. Roughly speaking, a point p in a data set is called a skyline if there is no point in the data set which ""dominates"" p. One of the problems addressed in my proposal is about estimating the expected number of skylines in n random points from a given d-dimensional set and studying the phase transition as d increases.*Due to the rapid expansion of the casino industry (including lotteries and online gaming), games of chance are now almost everywhere. One of the problems addressed in my proposal analyzes Hold'em Poker. Combinatorial, probabilistic, and game theoretical analyses are required to find the optimal (near-optimal) strategies. This has also become a hot topic in artificial intelligence.*Finding long cycles in a graph is a fundamental problem in graph theory and it also has many applications. The circumference of a graph G, denoted by c(G), is the length of a longest cycle in G. There are two long standing open problems about the best possible lower bound for c(G), one for 3-connected graphs with maximum degree at least 4, and the other for 3-connected cubic graphs. The current published bounds are still far away from the best possible bounds. I would like to obtain better bounds for both problems.*