Properties of extremal and random hypergraphs

这项研究建议解决组合学领域的基本问题，组合学是数学的一个分支，致力于研究离散结构。组合数学中的一个关键概念是图的概念。这是网络的抽象表示，由称为顶点的点组成，其中一些点对由称为边的线连接。这个定义给出了一个非常通用的概念，在数学和其他领域有广泛的应用。这一定义的实用性是本研究项目的动机，其主要焦点是研究超图的两个重要特征。我们研究的第一个特征是编辑距离。这是一个简单的度量，在给定两个具有相同顶点的图或超图的情况下，它提供了它们相似或不同的度量。像这样测量距离在许多环境中自然会出现，例如在研究代谢途径或生物学中的系统发育树时。我们的重点是超图与满足遗传性质的超图之间的距离(根据编辑距离)。对于图，Alon和Stav的一个开创性定理指出，最大距离是通过随机图来实现的，在随机图中，我们固定一组顶点，并在每对顶点之间以给定的概率随机添加边，而不依赖于其他边。相比之下，在超图的情况下对这个问题知之甚少；我们在这里的主要目标是理解这种情况并发展一个超图中的编辑距离理论来推广图的理论。我们研究的另一个特征是大型超图中是否包含大型固定结构。更准确地说，我们寻求在超图上找到确保它包含这种结构的条件。我们可以要求的一种简单的可能结构是一大批不重叠的边；我们称之为匹配。来自数学和其他学科不同领域的许多重要问题可以重新表述为在超图中寻找匹配，因此数学家们已经对确保给定大小匹配的条件有了一些理解(尽管许多重要问题仍然悬而未决)。然而，对于连通结构(在这种结构中，我们可以通过一系列重叠的边从任何边到任何其他边)，我们知道的要少得多。在最近的工作中，Pi和他的合著者开发了在超图中寻找大型连通结构的新技术，该项目的一个关键目标是进一步发展这些技术，并使用它们来解决这一领域的一系列公开问题。

This research proposal addresses fundamental questions in the field of combinatorics, a branch of mathematics devoted to the study of discrete structures. One key concept in combinatorics is the notion of a graph. This is an abstract representation of a network, consisting of points called vertices, some pairs of which are connected by lines called edges. Graphs can be used to model all kinds of real-world networks, both physical (e.g. telephone networks, road networks) and abstract (e.g. social networks, food chains), and consequently are exceptionally useful in applications. However, for many purposes it is unduly restrictive to only allow connections of pairs of vertices; this observation leads to the more general notion of a hypergraph, in which we allow edges of three or more vertices. This definition gives a highly versatile concept, with a wide range of applications within mathematics and other areas. The usefulness of this definition is the motivation for this research project, the main focus of which is to study two important characteristics of hypergraphs.The first characteristic we study is that of edit distance. This is a simple metric which, given two graphs or hypergraphs with the same vertices, provides a measure of how similar or different they are. Measuring distance like this arises naturally in many settings, for example in the study of metabolic pathways or phylogenetic trees in Biology. Our focus is on how far (in terms of edit distance) a hypergraph can be from hypergraphs satisfying a hereditary property. Here a hereditary property means a property such that even if we delete some vertices from the hypergraph then the part of the hypergraph which remains still satisfies the property; most useful characteristics of graphs and hypergraphs yield properties of this type. For graphs, a seminal theorem of Alon and Stav states that the maximum distance is attained by a random graph, in which we fix a set of vertices and add edges between each pair at random with a given probability and independently of other edges. By contrast, very little is known about this problem in the case of hypergraphs; our principal goal here is to understand this case and develop a theory of edit distances in hypergraphs which generalises the theory for graphs.The other characteristic which we study is whether a large hypergraph contains within it a large fixed structure. More precisely we seek to find conditions on the hypergraph which ensure that it contains this structure. One simple possible structure we could ask for is a large collection of non-overlapping edges; we call this a matching. Many important questions from diverse areas of mathematics and other disciplines can be rephrased in terms of finding matchings in hypergraphs, and consequently mathematicians have developed some understanding of conditions which ensure a matching of a given size (though many important questions remain open). However, for connected structures (in which we can get from any edge to any other edge by a sequence of overlapping edges) we know far less. In recent work the PI and his co-authors developed new techniques for finding large connected structures in hypergraphs, and a key goal of this project is to further develop these techniques and to use them to solve a range of open problems in this area.