Random Combinatorial Structures

离散组合结构的一个经典例子是图，而图论，包括其枚举方面，是组合学中最发达的部分之一。早在60年代，Erdos和Renyi在一系列开创性的论文中创造了现在被称为随机图论的理论，这是一个快速发展的研究领域，以枚举组合学和现代概率模型和技术的富有成效的相互作用而闻名。虽然Erdos-Renyi随机图处理是基于一个假设，即一个新的边缘位置是均匀随机选择的，但人们已经认识到，在一些应用（互联网网络）中，一个更现实的假设是偏向于更“流行”的顶点（节点），即所谓的优先依恋假设。支持者已经证明，在E-R过程的对应过程中，随机图经历了一个快速的转换，从小组件（集群）的海洋到小集群海洋中的巨大集群。倡议者计划研究图过程的后续阶段，例如k核的形成，以及图第一次连接的时刻。作者将在前人对E-R过程关键阶段的研究基础上，研究给定度分布的随机图上的顶点和边渗透过程，以及随机布尔方程的可解性。该计划包括与Alan Frieze（在E-R图的初始巨大组件上“混合”随机漫步的时间）和Nick Wormald （E-R过程的定向版本）的联合研究。其他问题包括：(i)由群体遗传学（“最近的共同祖先”）和计算机科学（Propp和Wilson提出的“过去的耦合”算法）中的问题，对“m个球到n个盒子”组合方案的预期合并时间进行详细的渐近研究；（ii）“排序网络”的枚举概率研究；（iii）关于子句长度为k2的随机布尔函数可满足性的“难解”组合问题的概率研究，如整数分割问题和k- sat问题。重要的是，除了其内在的数学价值外，所提出的研究计划还受到运筹学（双边劳动力市场），增长信息网络的概率建模，统计物理中的渗透过程以及组合算法的平均案例分析等相关领域出现的问题的推动。其中一些问题似乎特别适合作为支持者与博士生合作的研究课题。这种合作的过去的受益者是Adam Hammett和Craig Lennon，他们在2004年和2007年成功地为他们的博士论文辩护，这些论文是由NSF资助的。支持者相信，与他现在的学生John McSweeney和Jia Yeum的系统互动，将导致解决拟议方案中包含的两个问题，一个是关于分配模型的预期合并时间，另一个是关于随机方程的可解概率。

A classic example of a discrete combinatorial structure is a graph, and graph theory, including its enumerative aspect, is one of the most developed parts of combinatorics. Back in the sixties, in a series of pioneering papers Erdos and Renyi created what is now known as random graphs theory, a fast growing research area remarkable for fruitful interplay of enumerative combinatorics and modern probabilistic models and techniques. While Erdos-Renyi random graph process is based on assumption that a new edge location is chosen uniformly at random, it has been recognized that in some applications (internet networks) a more realistic assumption is of a bias toward more "popular" vertices (nodes), a so-called preferential attachment hypothesis. The proponent has proved that in this counterpart of the E-R process the random graph undergoes a rapid transformation, from a sea of small components (clusters) to a giant cluster in a sea of small clusters. The proponent plans to study the subsequent phases of the graph process, such as formation of a k-core, and the moment the graph first becomes connected. The proponent will study vertex and edge percolation processes on random graphs with a given degree distribution, and solvability of the random Boolean equations based on his previous studies of the E-R process at the critical stage. The program includes joint research with Alan Frieze ("mixing" time of a random walk on an incipient giant component of the E-R graph), and Nick Wormald (directed version of the E-R process). Among other problems are (i) a detailed asymptotic study of the expected coalescing time for a "m balls into n boxes" combinatorial scheme, motivated by problems in population genetics ("most recent common ancestor")and computer science ("coupling-from-the past" algorithm by Propp and Wilson);(ii) enumerative-probabilistic study of "sorting networks"; (iii) probabilistic study of "hard-to-solve" combinatorial problems, such as integer partitioning problem and a k-SAT problem, on satisfiability of a random Boolean function with clauses of length k 2.Importantly, besides its intrinsic mathematical value, the proposed research program is motivated by problems arising in related areas of operations research (two-sided labor markets), probabilistic modeling of growing information networks, percolation processes in statistical physics, and average case analysis of combinatorial algorithms. Some of these problems seem particularly suitable as research topics for the proponent's partnerships with PhD students. The past beneficiaries of such a collaboration were Adam Hammett and Craig Lennon who successfully defended their PhD theses on problems from the program funded by the NSF in 2004−2007. The proponent is confident that systematic interaction with his current students, John McSweeney and Jia Yeum, will lead to solving two problems included in the proposed program, one on the expected coalescing time for the allocation model,and another on probability of solvability of the random equations.