Probabilistic Combinatorics and Random Structures

点击翻译按钮获取中文摘要

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.