Properties of extremal and random hypergraphs

点击翻译按钮获取中文摘要

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.