Properties of extremal and random hypergraphs

这项研究计划解决了组合学领域的基本问题，组合学是数学的一个分支，专门研究离散结构。组合数学中的一个关键概念是图的概念。这是网络的抽象表示，由称为顶点的点组成，其中一些对由称为边的线连接。图可以用来模拟各种现实世界的网络，包括物理网络（如电话网络、道路网络）和抽象网络（如社交网络、食物链），因此在应用中非常有用。然而，对于许多目的来说，只允许顶点对的连接是不适当的限制;这一观察导致了超图的更一般的概念，其中我们允许三个或更多顶点的边。这个定义给出了一个高度通用的概念，在数学和其他领域有着广泛的应用。这个定义的有用性是本研究项目的动机，本研究项目的主要焦点是研究超图的两个重要特征。这是一个简单的度量，给定两个具有相同顶点的图或超图，它提供了一个度量它们有多相似或不同。像这样测量距离在许多环境中自然出现，例如在生物学中的代谢途径或系统发育树的研究中。我们的重点是多远（在编辑距离方面）超图可以从超图满足遗传特性。这里的遗传性质是指这样一种性质，即使我们从超图中删除一些顶点，超图的剩余部分仍然满足该性质;图和超图的大多数有用特征都产生这种类型的性质。对于图，Alon和Stav的一个开创性定理指出，最大距离是由随机图获得的，在随机图中，我们固定一组顶点，并以给定的概率随机添加每对边之间的边，并且与其他边无关。相比之下，很少有人知道这个问题的情况下，超图，我们的主要目标是了解这种情况下，并制定一个理论的编辑距离超图的理论推广的graphs.The其他特点，我们研究的是是否一个大型超图包含在它的一个大的固定结构。更确切地说，我们试图找到超图上的条件，以确保它包含这种结构。我们可以要求的一个简单的可能结构是一个非重叠边的大集合;我们称之为匹配。许多重要的问题，从不同领域的数学和其他学科可以重新措辞方面寻找匹配的超图，因此数学家已经发展了一些理解的条件，确保匹配的一个给定的大小（虽然许多重要的问题仍然开放）。然而，对于连通结构（我们可以通过一系列重叠边从任何边到任何其他边），我们知道的要少得多。在最近的工作中，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.