Substructures in large graphs and hypergraphs

在这个项目中，我们试图理解离散结构的基本数学性质。特别地，我们研究图，它是顶点的集合，以及一组称为边的无序顶点对。图被用来对交通网络、社交网络、大型数据集等建模，因此，更深入地了解图的基本属性有利于图的各种应用。这个项目属于极值图论的领域，其中一个主要方向是关于图之间的图参数的最小值和最大值，以避免某个子结构。该方案考虑这类问题，其中子结构是一个规定的小图或稀疏图的边缘不相交或顶点不相交副本的大集合；这些在该领域分别被称为包装和平铺问题。例如，这个项目的一部分是试图理解在给定边密度的图中可以不相交地填充的三角形的最大数量是多少。这个项目的第二部分涉及Jackson （c. 1980）关于在二部有向图中填充Hamilton环的一个著名猜想。有向图是通过指定每条边的方向而从图中获得的，Hamilton循环是顶点的循环排序，使得每两个连续的顶点都由一条边连接。最近证明了完全图的每一个正则方向都可以分解成这样的Hamilton环。我们试图证明Jackson的猜想，它是这个结果的一个自然的二部类比，并研究了Kuhn和Osthus关于三部图的一个相关猜想。最后，本项目的很大一部分致力于研究均匀密集超图中避免固定子超图的最大边密度。超图是图的自然概括，它允许对两个以上对象之间的关系进行建模。特别是，它们的边集由顶点的子集组成，这些顶点的大小不一定是2。我们试图理解，在一个特定的伪随机超图族中，什么样的边密度迫使一个给定的子超图出现。

In this project, we seek to understand the fundamental mathematical properties of discrete structures. In particular, we study graphs, which are collections of vertices, together with a set of unordered pairs of vertices called edges. Graphs are used to model transportation networks, social networks, large data sets, and more, and as such, a deeper understanding of their fundamental properties is beneficial to a wide variety of their applications.This project falls within the area of Extremal Graph Theory, in which one major direction concerns the minima and maxima of graph parameters among graphs avoiding a certain substructure. This project considers this type of problems, where the substructure is a large set of edge-disjoint or vertex-disjoint copies of a prescribed small or sparse graph; these are known in the area as packing and tiling problems, respectively. For example, part of this project seeks to understand what is the maximum number of triangles which can be packed edge-disjointly in a graph with a given density of edges.A second part of this project concerns a well-known conjecture of Jackson (c. 1980) on packing Hamilton cycles in bipartite oriented graphs. An oriented graph is obtained from a graph by specifying an orientation for each edge, and a Hamilton cycle is a cyclic ordering of the vertices such that every two consecutive vertices are connected by an edge. It was recently shown that every regular orientation of the complete graph can be decomposed into such Hamilton cycles. We seek to prove Jackson's conjecture, which is a natural bipartite analogue of this result, as well as investigate a related conjecture of Kuhn and Osthus on tripartite graphs.Finally, a significant portion of this project is dedicated to investigating the maximum edge-density in a uniformly dense hypergraph which avoids a fixed subhypergraph. Hypegraphs are a natural generalisation of graphs, which allows for the modelling of relationships among more than two objects. In particular, their edge set consists of subsets of vertices whose size is not necessarily two. We seek to understand, in a certain family of pseudorandom hypegraphs, what edge density forces the emergence of a given subhypergraph.