Hypergraph matchings

超图匹配

• 批准号: 1941813
• 金额: --
• 依托单位: University of Oxford
• 依托单位国家: 英国
• 项目类别: Studentship
• 财政年份: 2017
• 资助国家: 英国
• 起止时间: 2017 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=studentship-1941813
• 关键词: Hypergraph; matchings

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.

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