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属于F当且仅当G不包含这些子结构之一。这个不朽的定理在1983年至2004年发表的20篇论文中得到了证明,这些论文长达500多页。该证明有许多副作用,对该领域产生了独立的影响。图小定理的一个重要含义是上面的每个族F都可以通过有效的算法识别。此外,许多算法问题,被称为是NP-困难的一般被称为有效率的算法时,限制到这样一个家庭F.这个项目跟进藤原和Papasoglou和Bonamy等人最近的工作。重要的是,这个新定理不仅适用于图,而且适用于更广泛的度量空间,包括黎曼流形和计算机科学中出现的许多离散度量空间。我们设想一个粗糙的版本的经典图着色问题,将立即在计算几何问题的算法应用。这些问题的重要性,预计将增长由于就业的几何技术在数据科学。我们提出了图论中其他经典结果的几何类似物。在第二部分中,我们攻击了托马斯的一个众所周知的猜想,该猜想试图将罗伯逊-西摩图小定理扩展到可数无限图。我们观察到托马斯猜想对有限图也有重要的意义,并提出了一个更弱的版本,它仍然有这个意义,而且更容易被理解。我们提出了解决后者的具体步骤。

项目成果

期刊论文数量(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其他文献

Writing is not a soft skill
写作不是一项软技能
  • DOI:
  • 发表时间:
    2023
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Agelos Georgakopoulos
  • 通讯作者:
    Agelos Georgakopoulos
The planar Cayley graphs are effectively enumerable II
平面凯莱图是有效可枚举的 II
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
Graph theory in higher dimensions
高维图论
  • 批准号:
    EP/V009044/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 万元
  • 项目类别:
    青年科学基金项目
稀疏全基因组关联分析方法研究
  • 批准号:
    10926200
  • 批准年份:
    2009
  • 资助金额:
    10.0 万元
  • 项目类别:
    数学天元基金项目
保险风险模型、投资组合及相关课题研究
  • 批准号:
    10971157
  • 批准年份:
    2009
  • 资助金额:
    24.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
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了