Embeddings in Sparse Graphs

稀疏图中的嵌入

• 批准号: MR/S016325/1
• 负责人: Hong Liu
• 金额: $ 93.26万
• 依托单位: University of Warwick
• 依托单位国家: 英国
• 项目类别: Fellowship
• 财政年份: 2019
• 资助国家: 英国
• 起止时间: 2019 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=MR%2FS016325%2F1
• 关键词: Embeddings; Sparse; Graphs

Extremal combinatorics has witnessed a rapid growth in the past few decades. An archetype problem in this field is to study the structure of subgraphs appearing in different classes of graphs. Such problems are much better understand when the host graphs are dense thanks to a variety of tools applicable to dense graphs. This proposal will focus on such problems for sparse host graphs. In practice, almost all the graphs used to model real-life networks, such as facebook graphs, (artificial) neural networks, are sparse. The goal is to develop a theory of certain sublinear expanders that can be used to construct subgraphs with various properties in graphs with (sufficiently large) constant average degree. This project will connect sublinear expanders with two other central notions in combinatorics: cycles and topological minors. The theory developed will make decisive progress on central problems concerning embedding sparse subgraphs with additional arithmetic properties. Some of such problems have remained wide open since the 60s despite active attempts from various researchers. Further links will be sought via considering analogous problems in other areas such as number theory.

极值组合学在过去的几十年里发展迅速。这一领域的一个原型问题是研究出现在不同图类中的子图的结构。当宿主图是稠密的时，由于各种适用于稠密图的工具，这样的问题会更好地理解。这项建议将集中在稀疏主机图这样的问题。在实践中，几乎所有用于模拟现实网络的图，如facebook图，（人工）神经网络，都是稀疏的。我们的目标是发展一种理论，某些次线性扩张，可用于构建子图的各种性质的图（足够大）常数平均度。这个项目将连接次线性扩张与组合学中的其他两个中心概念：循环和拓扑子。开发的理论将取得决定性进展的核心问题，有关嵌入稀疏子图的额外的算术性能。自60年代以来，尽管各种研究人员进行了积极的尝试，但其中一些问题仍然是开放的。进一步的联系将寻求通过考虑类似的问题，在其他领域，如数论。

项目成果

On the rational Turán exponents conjecture

关于有理图兰指数猜想

• DOI: 10.1016/j.jctb.2020.12.003
• 发表时间: 2021
• 期刊: Journal of Combinatorial Theory, Series B
• 作者: Kang D

Countable graphs are majority 3-choosable

可数图是多数 3-可选

• DOI: 10.7151/dmgt.2383
• 发表时间: 2020
• 期刊: Discussiones Mathematicae Graph Theory
• 影响因子: 0.7
• 作者: Haslegrave J

Bivariate fluctuations for the number of arithmetic progressions in random sets

随机集中算术级数数的双变量波动

• DOI: 10.1214/19-ejp391
• 发表时间: 2019
• 期刊: Electronic Journal of Probability
• 影响因子: 1.4
• 作者: Barhoumi-Andréani Y

The number of maximum primitive sets of integers

最大原始整数集的数量

• DOI: 10.1017/s0963548321000018
• 发表时间: 2021
• 期刊: Combinatorics, Probability and Computing
• 作者: Liu H

Stability and exact Turán numbers for matroids

拟阵的稳定性和精确图兰数

• DOI: 10.1016/j.jctb.2019.11.004
• 发表时间: 2020
• 期刊: Journal of Combinatorial Theory, Series B
• 作者: Liu H