Probabilistic Combinatorics and Random Structures

随着互联网和许多社交网络的普及，随机图理论已经成为网络分析中不可或缺的工具。已经设计了各种随机图过程来模拟真实世界网络的演变。对随机图上算法的分析为这些算法在现实网络中的性能提供了理论支持。许多社交网络的行为与经典的Erdos-Renyi随机图模型(也称为二项随机图模型)非常不同。由于这个原因，新的(非齐次)随机图模型目前正受到极大的关注。特别是，研究人员对具有幂次序列的图感兴趣。在这个建议中，我解决了这一领域的两个问题：(A)使用指定的幂函数度序列来枚举图；以及(B)在Twitter上传播谣言(由一个带有度序列的随机有向图来建模，使得in-度遵循幂函数)。 我的建议中涉及的其他问题在随机图理论和概率组合学中具有重要意义。它们还与计算机科学和物理等其他研究学科密切相关。其中一些问题是理论计算机科学中的热点问题(如随机约束可满足性问题中的解聚类和随机图中的生成树填充)，另一些问题是随机图理论中的基本问题(不同随机图模型的等价性、k-核的稳定性和k-正则子图的出现阈值)。随机图理论中的一个显著现象是许多图的性质(或其他随机结构)呈现(尖锐的)相变。确定这样的相变在许多研究领域都是极其重要的。例如，许多CSP(如我的建议中所述)的解聚类阈值(即解空间从单个簇过渡到多个簇)被认为与它们的算法障碍相对应，这在计算机科学的算法设计中非常重要。由于对描述随机物体的相变的共同兴趣，随机图理论和物理学的研究有很大的重叠。例如，我提出的关于CSP聚类和k正则子图出现阈值的两个问题都已经被统计物理学家通过不严格的论证进行了广泛的研究。用随机图理论的严谨性来解决我提出的问题，也将在这些应用领域产生巨大的影响。 我的建议中的几个问题可以被视为分析真实世界网络的属性(例如，随机图中的生成树打包和Twitter上的谣言传播)。通过提供对大规模网络特性的鼓舞人心的见解，解决这些问题可能会使加拿大互联网公司受益。

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.