Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Waterloo

$31,000.00

Probabilistic Combinatorics and Random Structures

FY 2014-15

Summary
With the popularity of the Internet and many social networks, random graph theory has become an indispensable tool for network analysis. Various random graph processes have been designed to mimic the evolution of real-world networks. Analysis of algorithms on random graphs provides theoretical support for the performance of these algorithms in real-world networks. Many social networks behave very differently from the classical Erdos-Renyi random graph model (also known as the binomial random graph model). New (inhomogenous) random graph models are currently receiving great attention for this reason. In particular, researchers are interested in graphs with power-law degree sequences. In this proposal, I address two problems in this area: (a) enumerating graphs with a specified power-law degree sequence; and (b) rumor spreading on Twitter (modeled by a random directed graph with degree sequences such that the in-degrees follow a power law). The other problems addressed in my proposal have importance in random graph theory and probabilistic combinatorics. They are also closely related to other research disciplines like computer science and physics. Some of these problems are hot topics in theoretical computer science (e.g. solution clustering in random constraint satisfiablity problems (CSPs), and spanning-tree packing in random graphs) and some are fundamental problems in random graph theory (equivalence of different random graph models, the stability of k-cores, and the emergence threshold of k-regular subgraphs). A remarkable phenomenon in random graph theory is that many graph properties (or other random structures) exhibit (sharp) phase transitions. Determining such phase transitions is extremely important in many research areas. For instance, the solution clustering threshold (where the solution space transits from a single cluster to many clusters) of many CSPs (as addressed in my proposal) is believed to correspond to their algorithmic barrier, which is very important in algorithm design in computer science. Research in random graph theory and physics greatly overlaps due to the common interest in characterising phase transitions of random objects. For instance, the two problems in my proposal about CSP clustering and the k-regular subgraph emergence threshold have both been extensively investigated by statistical physicists, through non-rigorous arguments. Solving my proposed problems, with the rigour of random graph theory, will also have great impact in these applied areas. Several problems in my proposal can be viewed as analysing properties of real-world networks (e.g. spanning-tree packing in random graphs and rumour spreading on Twitter). Solving these problem will potentially benefit Canadian Internet companies by giving inspiring insights into properties of massive-scale networks.
Program
Discovery Grants Program - Individual
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2014-04678
Name nom
Gao, Pu
Department département
Combinatorics and Optimization
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2014
Competition year année de concours
2014
Award amount
31000
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
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
Research subject code
2713
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Algorithms
Research subject fr
Algorithmes
Partie
1
Nb partie
5
Application title
Probabilistic Combinatorics and Random Structures
Keyword
NSERC
Application summary
With the popularity of the Internet and many social networks, random graph theory has become an indispensable tool for network analysis. Various random graph processes have been designed to mimic the evolution of real-world networks. Analysis of algorithms on random graphs provides theoretical support for the performance of these algorithms in real-world networks. Many social networks behave very differently from the classical Erdos-Renyi random graph model (also known as the binomial random graph model). New (inhomogenous) random graph models are currently receiving great attention for this reason. In particular, researchers are interested in graphs with power-law degree sequences. In this proposal, I address two problems in this area: (a) enumerating graphs with a specified power-law degree sequence; and (b) rumor spreading on Twitter (modeled by a random directed graph with degree sequences such that the in-degrees follow a power law). The other problems addressed in my proposal have importance in random graph theory and probabilistic combinatorics. They are also closely related to other research disciplines like computer science and physics. Some of these problems are hot topics in theoretical computer science (e.g. solution clustering in random constraint satisfiablity problems (CSPs), and spanning-tree packing in random graphs) and some are fundamental problems in random graph theory (equivalence of different random graph models, the stability of k-cores, and the emergence threshold of k-regular subgraphs). A remarkable phenomenon in random graph theory is that many graph properties (or other random structures) exhibit (sharp) phase transitions. Determining such phase transitions is extremely important in many research areas. For instance, the solution clustering threshold (where the solution space transits from a single cluster to many clusters) of many CSPs (as addressed in my proposal) is believed to correspond to their algorithmic barrier, which is very important in algorithm design in computer science. Research in random graph theory and physics greatly overlaps due to the common interest in characterising phase transitions of random objects. For instance, the two problems in my proposal about CSP clustering and the k-regular subgraph emergence threshold have both been extensively investigated by statistical physicists, through non-rigorous arguments. Solving my proposed problems, with the rigour of random graph theory, will also have great impact in these applied areas. Several problems in my proposal can be viewed as analysing properties of real-world networks (e.g. spanning-tree packing in random graphs and rumour spreading on Twitter). Solving these problem will potentially benefit Canadian Internet companies by giving inspiring insights into properties of massive-scale networks.