Hypergraph matchings

描述：匹配理论是一个很大的领域，在实用算法和组合理论中都有很多研究方向。它提供了一个丰富而灵活的设置，其中包含了许多数学问题，通常是以意想不到的方式。它还通过大量算法的设计和复杂性理论的基础(超图匹配是Karp最初的NP完全问题之一)在运筹学和理论计算机科学中占据了基础地位。它的许多问题需要已知的图形结果的超图版本，而这些结果目前是未知的--这个项目将解决其中一些重要的公开问题。主要影响在于促进英国组合数学的研究环境，从而保持其良好的国际地位，并发展许多其他研究领域在寻找潜在数学理论的应用时所建立的基础。目的和目标：该项目旨在获得关于图中匹配的结果的超图概括，在各种环境中，例如确定性或随机的，以及在几个主题中，包括获得极端结果和理解典型结构。因此，它试图在当前组合学研究的几个方向上推倒知识的边界，并与该领域的重要趋势保持一致，例如提炼极值结果以获得结构结果，以及将思想从密集环境转移到稀疏(通常是随机的)环境。研究方法的新奇之处：研究方法寻求建立并进一步发展两个重要的和最新的想法，这两个想法在极值组合学中引发了许多令人兴奋的进展，即随机代数构造和迭代吸收。随机代数构造法是Keevash在2014年发展起来的，用来证明组合设计的存在猜想。迭代吸收，如库恩和奥斯萨斯，以及他们的许多合作者，代表了罗德尔，鲁辛斯基和斯梅雷迪吸收方法的最新改进，并在组合数学中证明了一系列猜想方面取得了惊人的成功(也是格洛克，库恩，罗和奥斯萨斯设计存在的新证明)。调整：这个项目属于EPSRC“逻辑和组合数学”研究范围内的“数学科学”。它与数字经济主题有关，通过组合学与理论计算机科学的接口，理论计算机科学已被反复确定为英国数学研究的优先领域，例如，2010年《国际数学科学评论》。

Description: Matching theory is a large field with many directions of research, both in practical algorithms and combinatorial theory. It provides a rich and flexible setting that incorporates many mathematical problems, often in unexpected ways. It has also occupied a fundamental position in Operations Research and Theoretical Computer Science, through the design of numerous algorithms, and the foundations of complexity theory (hypergraph matching was one of Karp's original list of NP-complete problems). Many of its questions require hypergraph versions of known results for graphs, which are currently unknown - this project will address some of these important open problems. The primary impact lies in contributing to the research environment in Combinatorics within the UK, thus maintaining its excellent international standing, and also developing the base on which numerous other fields of research build when finding applications of the underlying mathematical theory.Aims and objectives: This project aims to obtain hypergraph generalisations of results on matchings in graphs, in various settings, such as deterministic or random, and within several themes, including obtaining extremal results and understanding typical structures. As such, it seeks to push back the boundary of knowledge in several directions of current research in combinatorics, and is aligned with important trends in the field, such as refining extremal results to obtain structural results, and transferring ideas from dense settings to settings that are sparse (and often random).Novelty of the research methodology: The research methodology seeks to build on and further develop two important and very recent ideas that have sparked much exciting progress in Extremal Combinatorics, namely Randomised Algebraic Construction and Iterative Absorption. Randomised Algebraic Construction was developed in 2014 by Keevash to prove the Existence Conjecture for Combinatorial Designs. Iterative Absorption, as applied by Kuhn and Osthus, and many of their collaborators, represents the most recent refinement of the Absorbing Method of Rodl, Rucinski and Szemeredi, and had spectacular success in proving a range of conjectures in Combinatorics (and also a new proof of the Existence of Designs by Glock, Kuhn, Lo and Osthus).Alignment: This project falls within the EPSRC "Logic and Combinatorics" research area within "Mathematical Sciences". It is related to the Digital Economy Theme, through the interface of Combinatorics with Theoretical Computer Science, which has been repeatedly identified as a priority area for mathematical research in the UK, for example by the 2010 International Review of Mathematical Sciences.