Extremal and Structural Aspects of Graph Minor Theory
图小论的极值和结构方面
基本信息
- 批准号:RGPIN-2017-05010
- 负责人:
- 金额:$ 1.46万
- 依托单位:
- 依托单位国家:加拿大
- 项目类别:Discovery Grants Program - Individual
- 财政年份:2020
- 资助国家:加拿大
- 起止时间:2020-01-01 至 2021-12-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
The goal of this proposal is systematic investigation of extremal and structural properties of minor-closed classes of graphs. Graph minor theory is a deep and rich area of graph theory, initially developed by Robertson and Seymour in a series of twenty three papers. It continues to be an active area of research with extensive algorithmic applications. Some of the methods developed as part of the theory have been successfully used in practical computations.
One of the central results in graph minor theory is the graph structure theorem of Robertson and Seymour, which gives an approximate structural description of graphs that do not contain a fixed graph as a minor. The PI proposes to continue his ongoing long term joint project with Robin Thomas, the goal of which is a refinement of many aspects of this theory. In particular, one of the goals of the project is to obtain tight bounds on connectivity which guarantees existence of certain minors and related configurations (linkages, topological minors, etc.) in large graphs.
The PI also proposes investigation of extremal aspects of graph minor theory. One of the main goal of the proposal in this direction is to show that the density of every minor-closed class of graphs is attained by graphs of bounded pathwidth. The second goal is to compute density of particular minor-closed classes and develop generic tools for this type of problems.
Finally, the PI proposes to investigate relaxations of Hadwiger's conjecture. Hadwiger's conjecture is a longstanding open problem, which greatly strengthens the four-color theorem. It is possibly the most famous open problem in graph theory. The PI has recently announced a proof, joint with Zdenek Dvorak, of one relaxation of the conjecture, improving on earlier results of Kawarabayshi and Mohar, Wood, and Liu and Oum. The PI proposes to extend this result in several directions, in particular, investigating intriguing connections with bootstrap percolation, a concept investigated in probabilistic combinatorics and theoretical physics.
该提案的目的是对少量封闭图类别的极端和结构特性进行系统研究。图形理论是图理论的深层理论,最初是由罗伯逊和西摩开发的,其中有23篇论文。它仍然是具有广泛算法应用的研究领域。作为理论的一部分开发的一些方法已成功地用于实际计算中。
图形理论的核心结果之一是罗伯逊和西摩的图形结构定理,该定理给出了不包含固定图作为小调的图的近似结构描述。 PI提议继续与罗宾·托马斯(Robin Thomas)继续他正在进行的长期联合项目,其目标是对该理论的许多方面的完善。特别是,该项目的目标之一是获得有关连通性的紧密界限,以确保某些未成年人的存在和相关配置(链接,拓扑未成年人等)在大图中。
PI还提出了图形理论的极端方面的研究。该提案朝这个方向的主要目标之一是表明,通过有界路径的图,可以实现每个少量封闭的图形类别的密度。第二个目标是计算特定的次要类别的密度,并为这种类型的问题开发通用工具。
最后,PI提议研究哈德威格猜想的放松。 Hadwiger的猜想是一个长期存在的开放问题,它极大地增强了四色定理。这可能是图理论中最著名的开放问题。 PI最近宣布了与Zdenek Dvorak的联合证明,可以放松猜想,并改善了Kawarabayshi和Mohar,Wood,Liu和Oum的早期结果。 PI建议将此结果扩展到多个方向,特别是研究了与Bootstrap Percolation的有趣联系,这是一个在概率组合和理论物理学中研究的概念。
项目成果
期刊论文数量(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 }}
Norin, Sergey其他文献
The Spectrum of Triangle-Free Graphs
无三角形图的谱
- DOI:
10.1137/22m150767x - 发表时间:
2023 - 期刊:
- 影响因子:0.8
- 作者:
Balogh, József;Clemen, Felix Christian;Lidický, Bernard;Norin, Sergey;Volec, Jan - 通讯作者:
Volec, Jan
Counterexamples to a Conjecture of Harris on Hall Ratio
哈里斯霍尔比猜想的反例
- DOI:
10.1137/18m1229420 - 发表时间:
2022 - 期刊:
- 影响因子:0.8
- 作者:
Blumenthal, Adam;Lidický, Bernard;Martin, Ryan R.;Norin, Sergey;Pfender, Florian;Volec, Jan - 通讯作者:
Volec, Jan
Norin, Sergey的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Norin, Sergey', 18)}}的其他基金
Structure and Coloring of Sparse Graphs
稀疏图的结构和着色
- 批准号:
RGPIN-2022-03246 - 财政年份:2022
- 资助金额:
$ 1.46万 - 项目类别:
Discovery Grants Program - Individual
Extremal and Structural Aspects of Graph Minor Theory
图小论的极值和结构方面
- 批准号:
RGPIN-2017-05010 - 财政年份:2021
- 资助金额:
$ 1.46万 - 项目类别:
Discovery Grants Program - Individual
Extremal and Structural Aspects of Graph Minor Theory
图小论的极值和结构方面
- 批准号:
RGPIN-2017-05010 - 财政年份:2019
- 资助金额:
$ 1.46万 - 项目类别:
Discovery Grants Program - Individual
Extremal and Structural Aspects of Graph Minor Theory
图小论的极值和结构方面
- 批准号:
RGPIN-2017-05010 - 财政年份:2018
- 资助金额:
$ 1.46万 - 项目类别:
Discovery Grants Program - Individual
Extremal and Structural Aspects of Graph Minor Theory
图小论的极值和结构方面
- 批准号:
RGPIN-2017-05010 - 财政年份:2017
- 资助金额:
$ 1.46万 - 项目类别:
Discovery Grants Program - Individual
Semi-definite method in Combinatorics
组合学中的半定法
- 批准号:
418520-2012 - 财政年份:2016
- 资助金额:
$ 1.46万 - 项目类别:
Discovery Grants Program - Individual
Semi-definite method in Combinatorics
组合学中的半定法
- 批准号:
418520-2012 - 财政年份:2015
- 资助金额:
$ 1.46万 - 项目类别:
Discovery Grants Program - Individual
Semi-definite method in Combinatorics
组合学中的半定法
- 批准号:
418520-2012 - 财政年份:2014
- 资助金额:
$ 1.46万 - 项目类别:
Discovery Grants Program - Individual
Semi-definite method in Combinatorics
组合学中的半定法
- 批准号:
418520-2012 - 财政年份:2013
- 资助金额:
$ 1.46万 - 项目类别:
Discovery Grants Program - Individual
Semi-definite method in Combinatorics
组合学中的半定法
- 批准号:
418520-2012 - 财政年份:2012
- 资助金额:
$ 1.46万 - 项目类别:
Discovery Grants Program - Individual
相似国自然基金
非紧流形上辛结构唯一性问题的几个方面
- 批准号:
- 批准年份:2022
- 资助金额:30 万元
- 项目类别:青年科学基金项目
多功能POSS基纳米杂化材料分子结构设计及在革兰氏阴性菌诊疗方面的应用
- 批准号:52203176
- 批准年份:2022
- 资助金额:30.00 万元
- 项目类别:青年科学基金项目
非紧流形上辛结构唯一性问题的几个方面
- 批准号:12201039
- 批准年份:2022
- 资助金额:30.00 万元
- 项目类别:青年科学基金项目
非穿插三维共价有机框架材料的结构设计及在能源气体存储方面的应用研究
- 批准号:
- 批准年份:2022
- 资助金额:30 万元
- 项目类别:青年科学基金项目
多功能POSS基纳米杂化材料分子结构设计及在革兰氏阴性菌诊疗方面的应用
- 批准号:
- 批准年份:2022
- 资助金额:30 万元
- 项目类别:青年科学基金项目
相似海外基金
Combinational, Structural and algorithmic aspects of temporal graphs
时间图的组合、结构和算法方面
- 批准号:
2903280 - 财政年份:2024
- 资助金额:
$ 1.46万 - 项目类别:
Studentship
A structural elucidation technique of unknown substances with mass spectrometry, quantum chemistry, and chemical kinetics and its application to unknown growth substrates for pathogenic bacteria
利用质谱、量子化学和化学动力学解析未知物质的结构及其在病原菌未知生长基质中的应用
- 批准号:
23H03559 - 财政年份:2023
- 资助金额:
$ 1.46万 - 项目类别:
Grant-in-Aid for Scientific Research (B)
Development of Evaluation Method of Structural Performance of RC Buildings Considering Behavior during Earthquakes
考虑地震行为的RC建筑结构性能评价方法的开发
- 批准号:
22KJ1664 - 财政年份:2023
- 资助金额:
$ 1.46万 - 项目类别:
Grant-in-Aid for JSPS Fellows
Collaborative Research: Unraveling Structural and Mechanistic Aspects of RNA Viral Frameshifting Elements by Graph Theory and Molecular Modeling
合作研究:通过图论和分子建模揭示RNA病毒移码元件的结构和机制
- 批准号:
2151777 - 财政年份:2022
- 资助金额:
$ 1.46万 - 项目类别:
Continuing Grant
Collaborative Research: Unraveling Structural and Mechanistic Aspects of RNA Viral Frameshifting Elements by Graph Theory and Molecular Modeling
合作研究:通过图论和分子建模揭示RNA病毒移码元件的结构和机制
- 批准号:
2151859 - 财政年份:2022
- 资助金额:
$ 1.46万 - 项目类别:
Continuing Grant