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.

在这个项目中，我们试图了解离散结构的基本数学特性。特别是，我们研究图形，这些图是顶点的集合，以及一组无序的名为边缘的顶点。图形用于建模传输网络，社交网络，大数据集等等，因此，对其基本属性的更深入了解对它们的各种应用都有益。该项目属于极端图理论领域，其中一个主要方向涉及图形较小的图形参数，以避免在某些亚物体中避免图形参数。该项目考虑了这种类型的问题，其中子结构是规定的小或稀疏图的一组大型边缘 - 偶数或顶点 - 偶数副本；这些在该地区被称为包装和平铺问题。例如，该项目的一部分试图了解什么是最大数量的三角形数量，这些三角形数量可以将边缘夹在具有给定边缘密度的图表中。该项目的第二部分涉及杰克逊（Jackson）的众所周知的猜想（c。1980），涉及汉密尔顿（Hamilton）在杂货方面的图形中包装的汉密尔顿周期。通过指定每个边缘的方向获得方向的图形，汉密尔顿循环是对顶点的循环排序，以便每两个连续的顶点通过边缘连接。最近显示，完整图的每个规则方向都可以分解为这样的汉密尔顿周期。我们试图证明杰克逊的猜想是该结果的自然二手类似物，并研究了库恩和奥斯图斯在三方图上的相关猜想。本文中，该项目的很大一部分致力于研究均匀的密度高度的最大边缘密度，以避免了固定的子层。置于图形的自然概括，它允许对两个以上对象之间的关系进行建模。特别是，它们的边缘集由大小不一定为两个的顶点的子集组成。我们试图理解在某个伪和疏admegraphs的家族中，什么边缘密度迫使给定的亚液压的出现。