Sparse random combinatorial structures

点击翻译按钮获取中文摘要

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).