Minors at large
未成年人在逃
基本信息
- 批准号:EP/Y004302/1
- 负责人:
- 金额:$ 9.03万
- 依托单位:
- 依托单位国家:英国
- 项目类别:Research Grant
- 财政年份:2024
- 资助国家:英国
- 起止时间:2024 至 无数据
- 项目状态:未结题
- 来源:
- 关键词:
项目摘要
The Robertson-Seymour Graph Minor theorem is one of the deepest and most important results in Graph Theory. It asserts that every family F of graphs that is closed under the minor relation can be determined by a finite list of "forbidden" substructures, in the sense that a graph G belongs to F if and only if G does not contain one of these substructures. This monumental theorem was proved in a series of twenty papers spanning over 500 pages, published from 1983 to 2004. The proof had many side-results that have had an independent impact on the area. An important implication of the Graph Minor theorem is that every family F as above can be recognised by an efficient algorithm. Moreover, many algorithmic problems that are known to be NP-hard in general are known to have efficient algorithms when restricted to such a family F.This project follows up on recent work by Fujiwara & Papasoglou and Bonamy et al. to develop a "Coarse Graph Minor Theory" that parallels the classical graph minor theory but introduces a coarse perspective following Gromov's paradigm of coarse geometry. Importantly, this new theorem applies not only to graphs, but to a much broader classes of metric spaces including Riemannian manifolds and many discrete metric spaces arising in computer science. We envisage a coarse version of a classical graph colouring problem that would have immediate algorithmic applications in problems of computational geometry. The importance of such problems is expected to grow due to the employment of geometric techniques in data science. We propose geometric analogues of other classical results of graph theory. In a second part, we attack a well known-conjecture of Thomas that seeks to extend the Robertson-Seymour Graph Minor Theorem to countably infinite graphs. We objerve that Thomas' conjecture would have an important implication for finite graphs as well, and propose a weaker version that would still have this implication and is much more likely to be accessible. We propose concrete steps for attacking the latter.
Robertson-Seymour图小定理是图论中最深刻、最重要的结论之一。它断言在次要关系下闭合的图族F可以由一个有限的“禁止”子结构列表确定,即当且仅当G不包含这些子结构之一时,图G属于F。这个不朽的定理在1983年到2004年间发表的20多篇论文中得到了证明,跨度超过500页。这一证明有许多副作用,对该领域产生了独立的影响。图小定理的一个重要含义是,上面的每一个族F都可以被一个有效的算法识别。此外,许多已知的NP-hard算法问题在被限制到这样一个族f时,已知具有有效的算法。本项目在Fujiwara & Papasoglou和Bonamy等人最近的工作的基础上,开发了一个“粗图小理论”,该理论与经典的图小理论平行,但引入了一个遵循Gromov粗几何范式的粗视角。重要的是,这个新定理不仅适用于图,还适用于更广泛的度量空间类别,包括黎曼流形和计算机科学中出现的许多离散度量空间。我们设想了一个经典图形着色问题的粗略版本,它将在计算几何问题中具有直接的算法应用。由于几何技术在数据科学中的应用,这些问题的重要性预计会增加。我们提出了图论其他经典结果的几何类似物。在第二部分中,我们攻击托马斯的一个著名猜想,该猜想试图将罗伯逊-西摩图小定理扩展到可数无限图。我们观察到托马斯的猜想对有限图也有重要的含义,并提出了一个更弱的版本,仍然有这个含义,更有可能是可访问的。我们提出了打击后者的具体步骤。
项目成果
期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
数据更新时间:{{ journalArticles.updateTime }}
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Agelos Georgakopoulos其他文献
The planar Cayley graphs are effectively enumerable II
平面凯莱图是有效可枚举的 II
- DOI:
- 发表时间:
2019 - 期刊:
- 影响因子:0
- 作者:
Agelos Georgakopoulos;M. Hamann - 通讯作者:
M. Hamann
Writing is not a soft skill
写作不是一项软技能
- DOI:
- 发表时间:
2023 - 期刊:
- 影响因子:0
- 作者:
Agelos Georgakopoulos - 通讯作者:
Agelos Georgakopoulos
Brownian Motion on graph-like spaces
类图空间上的布朗运动
- DOI:
- 发表时间:
- 期刊:
- 影响因子:0
- 作者:
Agelos Georgakopoulos - 通讯作者:
Agelos Georgakopoulos
The planar cubic Cayley graphs
平面三次凯莱图
- DOI:
10.1090/memo/1190 - 发表时间:
2011 - 期刊:
- 影响因子:0
- 作者:
Agelos Georgakopoulos - 通讯作者:
Agelos Georgakopoulos
On walk-regular graphs and graphs with symmetric hitting times
- DOI:
- 发表时间:
2012-11 - 期刊:
- 影响因子:0
- 作者:
Agelos Georgakopoulos - 通讯作者:
Agelos Georgakopoulos
Agelos Georgakopoulos的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Agelos Georgakopoulos', 18)}}的其他基金
New Dimensions in Probability on Groups
群概率的新维度
- 批准号:
EP/V048821/1 - 财政年份:2021
- 资助金额:
$ 9.03万 - 项目类别:
Research Grant
Discrete Potential Theory and Applications
离散势理论及应用
- 批准号:
EP/L002787/1 - 财政年份:2013
- 资助金额:
$ 9.03万 - 项目类别:
Research Grant
相似国自然基金
水稻穗粒数调控关键因子LARGE6的分子遗传网络解析
- 批准号:
- 批准年份:2022
- 资助金额:30 万元
- 项目类别:青年科学基金项目
量子自旋液体中拓扑拟粒子的性质:量子蒙特卡罗和新的large-N理论
- 批准号:
- 批准年份:2020
- 资助金额:62 万元
- 项目类别:面上项目
甘蓝型油菜Large Grain基因调控粒重的分子机制研究
- 批准号:31972875
- 批准年份:2019
- 资助金额:58.0 万元
- 项目类别:面上项目
基于异构医学影像数据的深度挖掘技术及中枢神经系统重大疾病的精准预测
- 批准号:61672236
- 批准年份:2016
- 资助金额:64.0 万元
- 项目类别:面上项目
钙激活的大电流钾离子通道β1亚基影响慢性肾脏病进展的机制探讨
- 批准号:81070587
- 批准年份:2010
- 资助金额:38.0 万元
- 项目类别:面上项目
Large PB/PB小鼠 视网膜新生血管模型的研究
- 批准号:30971650
- 批准年份:2009
- 资助金额:8.0 万元
- 项目类别:面上项目
预构血管化支架以构建大体积岛状组织工程化脂肪瓣的实验研究
- 批准号:30901566
- 批准年份:2009
- 资助金额:19.0 万元
- 项目类别:青年科学基金项目
保险风险模型、投资组合及相关课题研究
- 批准号:10971157
- 批准年份:2009
- 资助金额:24.0 万元
- 项目类别:面上项目
稀疏全基因组关联分析方法研究
- 批准号:10926200
- 批准年份:2009
- 资助金额:10.0 万元
- 项目类别:数学天元基金项目
基因discs large在果蝇卵母细胞的后端定位及其体轴极性形成中的作用机制
- 批准号:30800648
- 批准年份:2008
- 资助金额:20.0 万元
- 项目类别:青年科学基金项目
相似海外基金
Renewal application: How do ecological trade-offs drive ectomycorrhizal fungal community assembly? Fine- scale processes with large-scale implications
更新应用:生态权衡如何驱动外生菌根真菌群落组装?
- 批准号:
MR/Y011503/1 - 财政年份:2025
- 资助金额:
$ 9.03万 - 项目类别:
Fellowship
SMILE - Semantic Modelling of Intent through Large-language Evaluations
SMILE - 通过大语言评估进行意图语义建模
- 批准号:
10097766 - 财政年份:2024
- 资助金额:
$ 9.03万 - 项目类别:
Collaborative R&D
How Large Earthquakes Change Our Dynamically Deforming Planet
大地震如何改变我们动态变形的星球
- 批准号:
DP240102450 - 财政年份:2024
- 资助金额:
$ 9.03万 - 项目类别:
Discovery Projects
Large Graph Limits of Stochastic Processes on Random Graphs
随机图上随机过程的大图极限
- 批准号:
EP/Y027795/1 - 财政年份:2024
- 资助金额:
$ 9.03万 - 项目类别:
Research Grant
LSS_BeyondAverage: Probing cosmic large-scale structure beyond the average
LSS_BeyondAverage:探测超出平均水平的宇宙大尺度结构
- 批准号:
EP/Y027906/1 - 财政年份:2024
- 资助金额:
$ 9.03万 - 项目类别:
Research Grant
Predicting how the inducible defences of large mammals to human predation shape spatial food web dynamics
预测大型哺乳动物对人类捕食的诱导防御如何塑造空间食物网动态
- 批准号:
EP/Y03614X/1 - 财政年份:2024
- 资助金额:
$ 9.03万 - 项目类别:
Research Grant
CSR: Small: Multi-FPGA System for Real-time Fraud Detection with Large-scale Dynamic Graphs
CSR:小型:利用大规模动态图进行实时欺诈检测的多 FPGA 系统
- 批准号:
2317251 - 财政年份:2024
- 资助金额:
$ 9.03万 - 项目类别:
Standard Grant
Collaborative Research: NSFGEO/NERC: After the cataclysm: cryptic degassing and delayed recovery in the wake of Large Igneous Province volcanism
合作研究:NSFGEO/NERC:灾难之后:大型火成岩省火山活动后的神秘脱气和延迟恢复
- 批准号:
2317936 - 财政年份:2024
- 资助金额:
$ 9.03万 - 项目类别:
Continuing Grant
Differentiating Cyclogenesis with and without Large Amplitude Mesoscale Gravity Waves: Implications for Rapidly Varying Heavy Precipitation and Gusty Winds
区分有和没有大振幅中尺度重力波的气旋发生:对快速变化的强降水和阵风的影响
- 批准号:
2334171 - 财政年份:2024
- 资助金额:
$ 9.03万 - 项目类别:
Continuing Grant
CRII: OAC: A Compressor-Assisted Collective Communication Framework for GPU-Based Large-Scale Deep Learning
CRII:OAC:基于 GPU 的大规模深度学习的压缩器辅助集体通信框架
- 批准号:
2348465 - 财政年份:2024
- 资助金额:
$ 9.03万 - 项目类别:
Standard Grant














{{item.name}}会员




