Embeddings in hypergraphs

由于组合数学与其他数学领域的广泛联系以及对其他科学学科的应用，组合数学领域近年来的声望急剧上升。它是许多理论计算机科学的基础，也是从根本上改变了我们日常生活的“数字革命”的基础。此外，物理学和生物学的进步都表明，我们周围的世界在本质上是离散的，组合工具对于增加我们的理解是至关重要的。更具体地说，这个建议涉及到超图的嵌入：什么时候可能在给定的超图中找到一些结构？一个简单的例子是匹配问题：给定某个超图G，我们可以选择G的最大边集M是什么，这样G的顶点不会位于M的一个以上成员中？或者更简单地说：在给定一些限制(由超边表示)的情况下，有多少人可以被分配到兼容的组中，哪些人可以组合在一起？这类问题通常很容易陈述，但为来自不同数学学科的许多重要问题提供了一个一般框架，这些学科包括最优化、数论、概率论、几何、代数和拓扑学。进一步说，匹配问题是理论计算机科学的一个基本问题(Karp最初的NP完全问题之一)，在该领域有着重要的应用，如分布式存储分配和图着色。它还与统计物理和计算化学有着重要的联系。到目前为止，人们对超图的这类问题了解得很少(而对图的情况了解得更多)，这一困难本质上与问题的计算难解性有关。然而，最近的进展和过去几年开发的新技术，包括我自己的一些工作，在这一领域开辟了许多新的方法；多年来进展甚微的关键的长期猜测正在朝着解决这些问题的方向迈出重大步伐。这一提议的主题是，这些进步加在一起，形成了超图嵌入的一般理论的开端。我的目的是进一步发展这一理论，其中将包括解决这一领域的几个关键问题。

The field of Combinatorics has seen a dramatic surge in prominence in recent years due to its extensive connections with other areas of mathematics and applications to other scientific disciplines. It is the foundation for much of Theoretical Computer Science, and so has underpinned the 'digital revolution' which has radically transformed our daily lives. Moreover, advances in both Physics and Biology have shown that much of the world around us is discrete in nature, and that combinatorial tools are crucial for increasing our understanding.More specifically, this proposal relates to embeddings in hypergraphs: when is it possible to find some structure within a given hypergraph? A simple example is the matching problem: given some hypergraph G, what is the largest set M of edges of G we can choose so that no vertex of G lies in more than one member of M? Or put more simply: how many people can be allocated into compatible groups, given some constraints (represented by hyperedges) on which combinations of people can be grouped together? Such problems are often very simple to state but provide a general framework for many important questions from a diverse range of mathematical subjects including Optimisation, Number Theory, Probability Theory, Geometry, Algebra and Topology. Further afield, the matching problem is a fundamental problem of Theoretical Computer Science (one of Karp's original NP-complete problems), with important applications in that field, such as for distributed storage allocation and graph colouring. It also has significant connections to Statistical Physics and Computational Chemistry.Until now, such problems have been poorly understood for hypergraphs (whereas much more is known for the graph case), a difficulty which is intrinsically connected to the computational intractability of the problem. However, recent advances and novel techniques developed over the past few years, including some of my own work, have opened up many new approaches in this area; crucial long-standing conjectures which had seen very little progress for many years are seeing major steps forward towards their solutions. The thesis of this proposal is that these advances, taken together, form the beginnings of a general theory of embeddings in hypergraphs. My aim is to further develop this theory, which will include the solution of several key problems in this area.