Substructures in large graphs and hypergraphs

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

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.