Sparse random combinatorial structures

更广泛的研究背景概率组合学是一门研究随机组合结构（如随机图、网络或矩阵）的数学学科。 这种随机结构在计算机科学和其他应用领域的随机结构中起着关键作用。 在过去的二十年中，概率组合学受到了统计物理学的推动，一种叫做“空腔方法”的启发式方法已经发展起来，对许多长期存在的问题提出了有趣的解释。 这个项目的目的是提供一个严格的数学基础的技术后，腔方法based.Research问题/ objectivesThe重点将是稀疏随机组合结构。 具体而言，该项目集中在三个突出的，密切相关的挑战：1。随机组合矩阵和离散代数结构上的随机方程2.稀疏随机图上的加权匹配3.稀疏随机图中的汉密尔顿圈。每个主题的目标是抓住统计物理的直觉来发展新的数学技术，并严格调查物理界提出的理论。具体来说，我们的目标是推导出稀疏随机组合矩阵是满秩的充分必要条件。 此外，我们将研究有限群上的随机方程组。第二个主题是稀疏随机图上的加权匹配问题。 诺贝尔物理学奖获得者Giorgio Parisi及其合著者最近提出了关于随机图上完美匹配的期望最小权重的显着preicse假设，我们的目标是严格调查。关于第三个主题，我们将利用物理直觉来解决稀疏但不规则的随机图上长期存在的汉密尔顿循环问题。方法/methodsIn这个项目中，我们的目标是利用在统计物理社区开发的直觉，开发新的方法来研究稀疏随机组合结构。 特别是，我们的目标是设计一个严格的数学基础的启发式方法中使用的物理社区，如信念传播消息传递algorithm.Level的独创性/创新通过比较以前的工作，我们调查的三个主题缺乏重要的对称性。 例如，固有的对称性使得在随机正则图中很容易找到和计数汉密尔顿圈。 但在不规则随机图中，汉密尔顿圈的存在性仍然是一个开放的问题。主要研究人员参与了这是一个联合FWF-DFG项目，由TU格拉兹的组合学小组（Mihyun Kang教授）和TU多特蒙德的有效算法和复杂性小组（Amin Coja-Oghlan教授）进行。

Wider research contextProbabilistic combinatorics is a mathematical discipline concerned with the study of random combinatorial structures such as random graphs, networks or matrices. Such random structures play a pivotal role in randomised constructions in computer science and other areas of application. Over the past two decades probabilistic combinatorics has received impulses from statistical physics, where a heuristic method called the "cavity method" has been developed to put forward intriguing conjectures on numerous long-standing problems. The aim of this project is to provide a rigorous mathematical basis for the techniques upon which the cavity method is based.Research questions / objectivesThe focus will be on sparse random combinatorial structures. Specifically, the project concentrates on three prominent, closely related challenges:1. random combinatorial matrices and random equations over discrete algebraic structures2. weighted matchings on sparse random graphs3. Hamilton cycles in sparse random graphs.The objective in each topic will be to seize upon statistical physics intuition to develop new mathematical techniques, and to rigorously investigate the conjectures put forward in the physics community.Specifically, we aim to derive tight necessary and sufficient conditions for a sparse random combinatorial matrix to be of full rank. Additionally, we are going to investigate random systems of equations over finite groups.The second topic will be the weighted matching problem on sparse random graphs. Physics Nobel laureate Giorgio Parisi and co-authors recently posited remarkably preicse conjectures as to the expected minimum weight of a perfect matching on a random graph that we aim to investigate rigorously.Concerning the third topic, we are going to utilise physics intuition to tackle the long-standing Hamilton cycle problem on sparse but irregular random graphs.Approach / methodsIn this project we aim to harness the intuition developed in the statistical physics community to develop new methods for the study of sparse srandom combinatorial structures. In particular, we aim to devise a rigorous mathematical basis for the heuristic methods used in the physics community, such as the Belief Propagation message passing algorithm.Level of originality / innovationBy comparison to prior work, the three topics that we investigate lack of crucial symmetry properties. For instance, inherent symmetry properties make it easy to find and count Hamilton cycles in random regular graphs. But in irregular random graphs, the existence of Hamilton cycles remains wide open.Primary researchers involvedThis is a joint FWF-DFG project conducted by the combinatorics group at TU Graz (Prof. Mihyun Kang) and the efficient algorithms and complexity group at TU Dortmund (Prof. Amin Coja-Oghlan).