Extremal and probabilistic combinatorics

极值和概率组合学

• 批准号: 2140269
• 金额: --
• 依托单位: University of Birmingham
• 依托单位国家: 英国
• 项目类别: Studentship
• 财政年份: 2018
• 资助国家: 英国
• 起止时间: 2018 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=studentship-2140269
• 关键词: Extremal; probabilistic; combinatorics

This project lies in the area of extremal and probabilistic combinatorics, and will address topical questions of interest in this field. These may include: (1) Dirac-type problems for quasi-random hypergraphs. There is a well-developed theory of quasi-random graphs and conditions which allow large subgraphs to be embedded within these graphs. Recently a more general classification of quasirandomness in hypergraphs has been established, bringing with it a range of interesting open problems regarding generalisations of embedding results to the hypergraph case. (2) Edit distances in graphs and hypergraphs. This is a well-studied metric on graphs and hypergraphs, for which there are still important open questions regarding, for example, the maximum edit distance of a graph or hypergraph (possibly of fixed density) from a given property. (3) Embeddings acyclic oriented graphs in tournaments. Several recent results have addressed embeddings of trees in tournaments, with the general question being to find for a given tree T the smallest n such that every tournament on n vertices contains a copy of T. This question generalises naturally by replacing `trees' with `oriented graphs not containing directed cycles', but little is known about this case so far. These topics are fundamental questions, aspects of which have attracted the attention of leading researchers around the world.

这个项目在于极值和概率组合学领域，并将解决在这一领域感兴趣的热门问题。其中包括：（1）拟随机超图的Dirac型问题。有一个成熟的理论，准随机图和条件，允许大子图嵌入这些图。最近，一个更一般的分类在超图的quasirandomity已经建立，带来了一系列有趣的公开问题，概括的嵌入结果的超图的情况下。(2)编辑图形和超图中的距离。这是一个关于图和超图的研究得很好的度量，对于这些图和超图，仍然存在重要的未决问题，例如，图或超图（可能具有固定密度）与给定属性的最大编辑距离。(3)竞赛图中无圈定向图的嵌入。最近的几个结果已经解决了嵌入树的比赛，一般的问题是找到一个给定的树T的最小n，使每个比赛的n个顶点包含一个副本的T。这个问题的推广自然取代“树”与“有向图不包含有向循环”，但鲜为人知的是，这种情况下至今。这些主题是基本问题，其各个方面吸引了世界各地领先研究人员的注意。