Probabilistic and Extremal Combinatorics

这方面的研究主要集中在概率组合数学领域，包括随机组合结构、随机算法和组合数学的概率存在证明(即概率方法)的研究。近年来，这一领域见证了一种技术的发展，该技术用于证明离散随机过程的关键统计数据随着过程的演变可能保持在其预期轨迹附近。这种方法被称为用于贪婪算法和随机图过程的微分方程组方法。研究人员最近将这一技术扩展到分析无三角形过程，这是一种在无三角形图空间上产生有趣分布的“受控”随机图过程。研究人员指出，根据这种分布绘制的图很可能在一个尽可能小的恒定乘性因子内具有独立数。换句话说，这个无三角形的过程会产生一个Ramsey R(3，t)图。调查者应继续发展这一方法，以研究相关的“受控”随机过程，重点放在从极值组合学的角度来看感兴趣的过程。相关问题是由计算机科学推动的。在这里，研究者试图开发微分方程法的应用来证明随机算法的良好性能，而不需要相关微分方程解的显式解或数值近似(需要这样的信息通常使该方法的应用变得非常复杂)。本研究项目是对离散数学对象的研究，例如网络或代码，其随时间的演变由一系列随机选择决定。我们对在不同回合中作出的选择之间存在依赖关系的进程特别感兴趣。虽然这样的过程可以很好地模拟真实世界现象的动力学，比如疾病在网络中的传播或材料中的相变，但这项研究的重点是产生有趣的数学对象的过程。长期以来，随机性在构造复杂的组合对象中扮演着重要的角色，就像随机性在计算机科学的许多算法中扮演着核心角色一样。这项研究预计将在多个领域产生影响，因为调查人员将开发通用工具，以了解这些系统随时间的演变。

The majority of this research is in the area of probabilistic combinatorics, which is comprised of the study of random combinatorial structures, randomized algorithms and probabilistic existence proofs for combinatorics (i.e. the probabilistic method). In recent years, this field has seen the development of a technique for proving that key statistics of a discrete stochastic process are likely to remain close to their expected trajectories as the process evolves. This method is known as the differential equations method for greedy algorithms and random graph processes. The investigator recently extended this technique to analyze the triangle-free process, a `controlled' random graph process that produces an interesting distribution on the space of triangle-free graphs. The investigator showed that a graph drawn from this distribution is likely to have independence number within a constant multiplicative factor of the smallest possible. In other words, the triangle-free process produces a Ramsey R(3,t) graph. The investigator shall continue the development of this method for the study of related `controlled' random processes, with an emphasis on processes that are interesting from the perspective of extremal combinatorics. Related questions are motivated by computer science. Here the investigator attempts to develop applications of the differential equations method to prove good performance of randomized algorithms without an explicit solution, or numerical approximation of the solution, of the associated differential equation (the need for such information often significantly complicates application of this method).This research project is an investigation of discrete mathematical objects, like networks or codes, whose evolution over time is determined by a sequence of random choices. We are particularly interested in processes where there is dependence between the choices made in different rounds. While such processes can be good models for the dynamics of real-world phenomenon, like the spread of a disease in a network or phase transitions in materials, the focus of this research is on processes that generate interesting mathematical objects. Randomness has long played an important role in the construction of sophisticated combinatorial objects, just as randomness plays an a central role in many algorithms in computer science. This research is expected to have an impact in multiple domains as the investigator shall develop general tools for understanding the evolution of these systems over time.