Local-Global Interactions in Combinatorics

组合学中的局部-全局相互作用

• 批准号: EP/V007327/1
• 负责人: Alexander Scott
• 金额: $ 63.69万
• 依托单位: University of Oxford
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2021
• 资助国家: 英国
• 起止时间: 2021 至 无数据
• 项目状态: 未结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FV007327%2F1
• 关键词: Local; Global; Interactions; Combinatorics

A fundamental question in many parts of the mathematical sciences is how local and global structure interact. For instance, what can we say about the local structures of a large, complicated network? How is global structure constrained by what we see locally? Problems of this type arise in many areas, including for example model theory, geometric group theory, topology, combinatorics, computer science, statistical physics, biology, probability, network science, and data analysis. Practical examples include DNA sequencing, where fragments of a genetic sequence need to be assembled to a global sequence, and problems in big data, where the global structure is too large to access directly and its properties must be inferred from 'local' information. The aim of this research is to address fundamental questions about the relationship between local and global structure in graphs and networks. This will generate new theory and new structural understanding, as well as leading to new insights into the analysis of algorithms.

在数学科学的许多领域，一个基本问题是局部结构和全局结构如何相互作用。例如，对于一个大型复杂网络的局部结构，我们能说些什么呢？全球结构是如何受到局部情况的制约的？这类问题出现在许多领域，包括模型论、几何群论、拓扑学、组合学、计算机科学、统计物理、生物学、概率论、网络科学和数据分析。实际的例子包括DNA测序，其中基因序列的片段需要组装成一个全局序列，以及大数据中的问题，其中全局结构太大而无法直接访问，其属性必须从“局部”信息中推断出来。本研究的目的是解决关于图和网络中局部和全局结构之间关系的基本问题。这将产生新的理论和新的结构理解，并导致对算法分析的新见解。

项目成果

Induced $C_4$-free subgraphs with large average degree

导出具有大平均度的无 $C_4$ 子图

• DOI: 10.48550/arxiv.2307.08361
• 发表时间: 2023
• 作者: Du X

Bipartite graphs with no K6 minor

没有 K6 小调的二分图

• DOI: 10.1016/j.jctb.2023.08.005
• 发表时间: 2024
• 期刊: Journal of Combinatorial Theory, Series B
• 作者: Chudnovsky M

On tree decompositions whose trees are minors

关于次树的树分解

• DOI: 10.1002/jgt.23083
• 发表时间: 2024
• 期刊: Journal of Graph Theory
• 影响因子: 0.9
• 作者: Blanco P

Pure pairs. X. Tournaments and the strong Erdos-Hajnal property

纯对。

• DOI: 10.1016/j.ejc.2023.103786
• 发表时间: 2024
• 期刊: European Journal of Combinatorics
• 影响因子: 1
• 作者: Chudnovsky M

Polynomial bounds for chromatic number VII. Disjoint holes

色数 VII 的多项式界限。

• DOI: 10.1002/jgt.22987
• 发表时间: 2023
• 期刊: Journal of Graph Theory
• 影响因子: 0.9
• 作者: Chudnovsky, Maria;Scott, Alex;Seymour, Paul;Spirkl, Sophie
• 通讯作者: Spirkl, Sophie