Problems in Randomized Algorithms, Random Graphs, and Computational Geometry

随机算法、随机图和计算几何中的问题

• 批准号: RGPIN-2019-04269
• 负责人: Delcourt, Michelle
• 金额: $ 2.06万
• 依托单位: Ryerson University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=682980
• 关键词: Problems; Randomized; Algorithms; Random; Graphs

The overarching goal of my research program is to solve a number of long standing open problems in the intersection of theoretical computer science, graph theory, and probability theory. A commonality between the proposed topics is the use of probabilistic techniques. More precisely, my proposed research program focuses on the following areas.******(Objective 1) Randomized algorithms. Although counting the number of proper k-colourings of a graph is a computationally hard problem, Jerrum, Valiant, and Vazirani showed that a nearly uniform sampler gives rise to an approximate enumeration, motivating the question of finding an algorithm to efficiently generate uniformly random proper colourings of a graph; this is a central topic in both computer science and statistical physics. My colleagues and I made a recent breakthrough, the first progress on the most important question in this area in 19 years. My students and I will push this approach further, both working on the fundamental problem for Glauber dynamics and using similar techniques to bound the mixing time of other Markov chains as well.******(Objective 2) Random regular graphs. A question that has attracted much interest in graph theory is: under what conditions can we partition the edge set of a graph into edge disjoint copies of a subgraph? This is fundamentally related to some of the most notorious open areas of research such as finding orientations of certain types, nowhere-zero flows, and colourings of planar graphs. A key new insight is that moving long standing problems from structural graph theory to the random regular setting can provide additional machinery and help to shed light on classical, longstanding problems. For instance using probabilistic techniques, a coauthor and I recently showed that a random 4-regular graph has a decomposition into 3-stars asymptotically almost surely. An important line of research with far reaching applications is generalizing this result in various ways. My students and I will pursue developing methods for k-stars in d-regular random graphs as well as decompositions into other trees.******(Objective 3) Computational geometry. An active line of inquiry in combinatorics in recent years has been extending classical results to the so-called sparse random setting, where the goal is to show that certain known properties of “dense” combinatorial structures are inherited by their randomly chosen “sparse” substructures. In this spirit my team and I will develop an algorithmic approach that shows if a given algebraic hypergraph is “dense” in a certain sense, then a generic low-dimensional subset of the vertices induces a subhypergraph that is also “dense.” Such results have applications in computational geometry and matroid theory. My team and I will also establish a natural generalization of the classical dimension of fibers theorem in algebraic geometry, a result interesting in its own right.

我的研究计划的总体目标是在理论科学的交叉点和概率理论中解决许多长期的开放问题）随机算法是一个计算困难的问题，jerrum，valiance和vazirani表明，整齐的均匀采样器会导致图表的近似枚举我和同事们在19 19的这一领域中取得了进步，我和我的学生都会推动Glauber动态。 ***（客观2）随机图表，将图形的副本集成一团，这与某些最臭名昭著的开放区域相关，这是某些类型的开放区域的基础这是从结构图理论到随机设置的长期立场，可以提供更多的机制，并有助于阐明经典的长期问题在遥不可及的应用程序中，我的学生将概括此结果在最近的稀疏随机设置中，组合术中的主动询问线是“ dene”组合结构的已知特性，它是由它们随机选择的“稀疏”子结构所继承的。表明给定的代数超图是“密集”，那么顶点的目标子集诱导了“密集”的亚液压，在计算机几何学和矩阵几何学中都有应用。