Random Combinatorial Structures

离散组合结构的一个经典例子是图，而图论，包括它的计数方面，是组合学中最发达的部分之一。早在60年代，鄂尔多斯和仁义在一系列开创性的论文中创造了现在被称为随机图理论的东西，这是一个快速增长的研究领域，以列举组合学与现代概率模型和技术的卓有成效的相互作用而闻名。虽然Erdos-Renyi随机图过程是基于这样的假设，即新的边位置是随机选择的，但人们已经认识到，在某些应用(互联网网络)中，更现实的假设是偏向更“流行”的顶点(节点)，即所谓的优先依附假设。支持者已经证明，在这个E-R过程的对应物中，随机图经历了一个快速的转变，从一个小组件(集群)的海洋变成了一个小集群海洋中的一个巨型集群。倡导者计划研究图表过程的后续阶段，如k核的形成，以及图表第一次连接的时刻。提出者将研究具有给定度分布的随机图上的点渗流过程和边渗流过程，以及基于他以前对关键阶段E-R过程的研究的随机布尔方程的可解性。该计划包括与Alan Frieze(在E-R图的初始巨型分量上随机行走的“混合”时间)和Nick WorMald(E-R过程的定向版本)的联合研究。其他问题包括：(I)在群体遗传学(“最近的共同祖先”)和计算机科学(Propp和Wilson的“过去的耦合”算法)问题的推动下，对“m球成n盒”组合方案的预期合并时间的详细渐近研究；(Ii)“分类网络”的枚举-概率研究；(3)“难解”组合问题的概率研究，如整数划分问题和k-SAT问题，关于子句长度为k 2的随机布尔函数的可满足性的概率研究。重要的是，除了其内在的数学价值外，所提出的研究计划还受到运筹学(双边劳动力市场)、增长信息网络的概率建模、统计物理中的渗流过程和组合算法的平均案例分析等相关领域中的问题的推动。其中一些问题似乎特别适合作为提倡者与博士生合作的研究主题。过去这种合作的受益者是亚当·哈米特和克雷格·列侬，他们成功地为他们的博士论文辩护，他们的博士论文是关于NSF在2004年和2007年资助的项目中的问题。支持者相信，与他目前的学生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.