Substructures in large graphs and hypergraphs

大图和超图的子结构

基本信息

批准号：
EP/V038168/1
负责人：
Yanitsa Pehova
金额：
$ 26.57万
依托单位：
London School of Economics and Political Science
依托单位国家：
英国
项目类别：
Fellowship
财政年份：
2022
资助国家：
英国
起止时间：
2022 至无数据
项目状态：
未结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FV038168%2F1
关键词：
Substructures large graphs 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.

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