Theory of graph homomorphisms and extremal combinatorics
图同态和极值组合理论
基本信息
- 批准号:408045-2011
- 负责人:
- 金额:$ 1.31万
- 依托单位:
- 依托单位国家:加拿大
- 项目类别:Discovery Grants Program - Individual
- 财政年份:2015
- 资助国家:加拿大
- 起止时间:2015-01-01 至 2016-12-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
Discrete mathematics or combinatorics is a fundamental mathematical discipline
which focuses on the study of discrete objects and their properties. This area which is as old as
the human ability to count, has attracted many strong mathematicians and is experiencing tremendous growth during the last fifty years. One of the main reasons for this is its intimate connection with computer science, the utility of which is obvious. Moreover combinatorics has applications to probability, set theory, cryptography, communication theory, the geometry of Banach spaces, harmonic analysis, number theory, ... the list goes on and on.
However, still many of these applications would fail to impress many mathematicians who regard combinatorics as a large collection of isolated results and problems that can be disregarded as technical part of mathematics. This I believe is mainly due to the fact there has not been much theory developed to connect these results and problems to each other. However, in the last decade, this has started to change, and this change has gained more speed recently.
A significant part of modern extremal combinatorics is dedicated to the study of the asymptotic relations between subgraph densities. These relations are usually expressed as algebraic inequalities between subgraph densities. Despite the variety of ingenious and hard results in asymptotic graph theory, surprisingly, there seem to exist only a handful of essentially different techniques in this area, and many known results are proven by clever combinations these techniques and tools.
In recent years a new line of researches in the direction of developing theories that explains these similarities in the proofs of various seemingly very different results in this area has emerged. The purpose of this line of research is to develops a general theory that (1) reveals the general nature of this area of mathematics (2) encompasses the main techniques used in this area and provides methods for applying them in an automated manner (3) provides new tools for solving the large collection of open problems in this area.
The problems that I am working on are the general problems that reveal the limitations and powers of these theories. These problems if solved will increase our general understanding of the nature of the area of extremal combinatorics.
An important result in this area says that many theorems follow from the positive semi-definiteness of a certain infinite matrix. This positive semi-definite characterization is a powerful approach for proving such inequalities. This method is very convenient to program, so that the search for ``right'' relations can be to a large degree computerized. In other words, in this area certain type of problems which were previously solved by tedious work of important mathematics can now be solved by a computer problems.
I have already used this method to solve an open problem, and in the future I am planning to combine this method with other auxiliary tools and techniques to attack to various open problems in extremal graph theory.
离散数学或组合数学是一门基础数学学科
它专注于离散对象及其属性的研究。这片区域的历史
人类的计数能力,吸引了许多强大的数学家,并在过去的五十年里经历了巨大的增长。其中一个主要原因是它与计算机科学的密切联系,其实用性是显而易见的。 此外,组合数学的应用概率,集合论,密码学,通信理论,几何的Banach空间,调和分析,数论,...这样的例子不胜枚举。
然而,仍然有许多这些应用程序将无法打动许多数学家谁认为组合数学作为一个大集合的孤立的结果和问题,可以忽略作为技术的一部分数学。我认为这主要是由于还没有太多理论来将这些结果和问题相互联系起来。然而,在过去十年中,这种情况开始发生变化,最近这种变化的速度更快。
现代极值组合学的一个重要部分是致力于研究子图密度之间的渐近关系。这些关系通常表示为子图密度之间的代数不等式。尽管各种巧妙的和困难的结果在渐近图论,令人惊讶的是,似乎只存在少数本质上不同的技术在这一领域,许多已知的结果证明了这些技术和工具的巧妙组合。
近年来,在发展理论的方向上出现了一条新的研究路线,这些理论在证明这一领域各种看似非常不同的结果时解释了这些相似之处。这条研究路线的目的是开发一个通用理论,(1)揭示数学这一领域的一般性质(2)包括这一领域使用的主要技术,并提供以自动化方式应用它们的方法(3)提供新的工具来解决这一领域的大量开放问题。
我正在研究的问题是揭示这些理论的局限性和力量的一般问题。这些问题的解决将增加我们对极值组合学领域性质的一般理解。
在这方面的一个重要结果说,许多定理遵循的积极半定的某一无限矩阵。这种半正定特征是证明此类不等式的有力方法。这种方法编程非常方便,因此寻找“正确”关系在很大程度上可以计算机化。换句话说,在这方面的某些类型的问题,以前解决了繁琐的工作,重要的数学,现在可以解决的计算机问题。
我已经用这种方法解决了一个开放的问题,在未来,我计划联合收割机这种方法与其他辅助工具和技术,以攻击极端图论中的各种开放问题。
项目成果
期刊论文数量(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 }}
Hatami, Hamed其他文献
Online Learning and Disambiguations of Partial Concept Classes
部分概念类的在线学习与消歧
- DOI:
10.4230/lipics.icalp.2023.42 - 发表时间:
2023 - 期刊:
- 影响因子:0
- 作者:
Cheung, Tsun-Ming;Hatami, Hamed;Hatami, Pooya;Hosseini, Kaave - 通讯作者:
Hosseini, Kaave
The Implicit Graph Conjecture is False
隐式图猜想是错误的
- DOI:
- 发表时间:
2022 - 期刊:
- 影响因子:0
- 作者:
Hatami, Hamed;Hatami, Pooya - 通讯作者:
Hatami, Pooya
Graph norms and Sidorenko's conjecture
- DOI:
10.1007/s11856-010-0005-1 - 发表时间:
2010-01-01 - 期刊:
- 影响因子:1
- 作者:
Hatami, Hamed - 通讯作者:
Hatami, Hamed
A counter-example to the probabilistic universal graph conjecture via randomized communication complexity
通过随机通信复杂性的概率通用图猜想的反例
- DOI:
10.1016/j.dam.2022.07.023 - 发表时间:
2022 - 期刊:
- 影响因子:1.1
- 作者:
Hambardzumyan, Lianna;Hatami, Hamed;Hatami, Pooya - 通讯作者:
Hatami, Pooya
Importance of lactate dehydrogenase (LDH) and monocarboxylate transporters (MCTs) in cancer cells.
- DOI:
10.1002/hsr2.996 - 发表时间:
2023-01 - 期刊:
- 影响因子:2
- 作者:
Hatami, Hamed;Sajedi, Atefe;Mir, Seyed Mostafa;Memar, Mohammad Yousef - 通讯作者:
Memar, Mohammad Yousef
Hatami, Hamed的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Hatami, Hamed', 18)}}的其他基金
Structural theorems in communication complexity
通信复杂性的结构定理
- 批准号:
RGPIN-2022-03745 - 财政年份:2022
- 资助金额:
$ 1.31万 - 项目类别:
Discovery Grants Program - Individual
Analytic techniques in communication complexity, information complexity, and property testing
通信复杂性、信息复杂性和属性测试的分析技术
- 批准号:
RGPIN-2016-05807 - 财政年份:2021
- 资助金额:
$ 1.31万 - 项目类别:
Discovery Grants Program - Individual
Analytic techniques in communication complexity, information complexity, and property testing
通信复杂性、信息复杂性和属性测试的分析技术
- 批准号:
RGPIN-2016-05807 - 财政年份:2020
- 资助金额:
$ 1.31万 - 项目类别:
Discovery Grants Program - Individual
Analytic techniques in communication complexity, information complexity, and property testing
通信复杂性、信息复杂性和属性测试的分析技术
- 批准号:
RGPIN-2016-05807 - 财政年份:2019
- 资助金额:
$ 1.31万 - 项目类别:
Discovery Grants Program - Individual
Analytic techniques in communication complexity, information complexity, and property testing
通信复杂性、信息复杂性和属性测试的分析技术
- 批准号:
RGPIN-2016-05807 - 财政年份:2018
- 资助金额:
$ 1.31万 - 项目类别:
Discovery Grants Program - Individual
Analytic techniques in communication complexity, information complexity, and property testing
通信复杂性、信息复杂性和属性测试的分析技术
- 批准号:
RGPIN-2016-05807 - 财政年份:2017
- 资助金额:
$ 1.31万 - 项目类别:
Discovery Grants Program - Individual
Analytic techniques in communication complexity, information complexity, and property testing
通信复杂性、信息复杂性和属性测试的分析技术
- 批准号:
RGPIN-2016-05807 - 财政年份:2016
- 资助金额:
$ 1.31万 - 项目类别:
Discovery Grants Program - Individual
Theory of graph homomorphisms and extremal combinatorics
图同态和极值组合理论
- 批准号:
408045-2011 - 财政年份:2014
- 资助金额:
$ 1.31万 - 项目类别:
Discovery Grants Program - Individual
Theory of graph homomorphisms and extremal combinatorics
图同态和极值组合理论
- 批准号:
408045-2011 - 财政年份:2013
- 资助金额:
$ 1.31万 - 项目类别:
Discovery Grants Program - Individual
Theory of graph homomorphisms and extremal combinatorics
图同态和极值组合理论
- 批准号:
408045-2011 - 财政年份:2012
- 资助金额:
$ 1.31万 - 项目类别:
Discovery Grants Program - Individual
相似国自然基金
基于Graph-PINN的层结稳定度参数化建模与沙尘跨介质耦合传输模拟研
- 批准号:
- 批准年份:2025
- 资助金额:0.0 万元
- 项目类别:省市级项目
平面三角剖分flip graph的强凸性研究
- 批准号:12301432
- 批准年份:2023
- 资助金额:30.00 万元
- 项目类别:青年科学基金项目
基于graph的多对比度磁共振图像重建方法
- 批准号:61901188
- 批准年份:2019
- 资助金额:24.5 万元
- 项目类别:青年科学基金项目
基于de bruijn graph梳理的宏基因组拼接算法开发
- 批准号:61771009
- 批准年份:2017
- 资助金额:50.0 万元
- 项目类别:面上项目
基于Graph和ISA的红外目标分割与识别方法研究
- 批准号:61101246
- 批准年份:2011
- 资助金额:22.0 万元
- 项目类别:青年科学基金项目
固定参数可解算法在平面图问题的应用以及和整数线性规划的关系
- 批准号:60973026
- 批准年份:2009
- 资助金额:32.0 万元
- 项目类别:面上项目
图的一般染色数与博弈染色数
- 批准号:10771035
- 批准年份:2007
- 资助金额:18.0 万元
- 项目类别:面上项目
中国Web Graph的挖掘与应用研究
- 批准号:60473122
- 批准年份:2004
- 资助金额:23.0 万元
- 项目类别:面上项目
组合设计及其大集
- 批准号:10371031
- 批准年份:2003
- 资助金额:20.0 万元
- 项目类别:面上项目
相似海外基金
Computational complexity of combinatorial problems: graph homomorphisms, packings, and good characterizations
组合问题的计算复杂性:图同态、打包和良好的表征
- 批准号:
RGPIN-2014-04760 - 财政年份:2022
- 资助金额:
$ 1.31万 - 项目类别:
Discovery Grants Program - Individual
Computational complexity of combinatorial problems: graph homomorphisms, packings, and good characterizations
组合问题的计算复杂性:图同态、打包和良好的表征
- 批准号:
RGPIN-2014-04760 - 财政年份:2021
- 资助金额:
$ 1.31万 - 项目类别:
Discovery Grants Program - Individual
Edge-coloured graph homomorphisms to cycles
边缘彩色图与循环的同态
- 批准号:
550575-2020 - 财政年份:2020
- 资助金额:
$ 1.31万 - 项目类别:
University Undergraduate Student Research Awards
Computational complexity of combinatorial problems: graph homomorphisms, packings, and good characterizations
组合问题的计算复杂性:图同态、打包和良好的表征
- 批准号:
RGPIN-2014-04760 - 财政年份:2020
- 资助金额:
$ 1.31万 - 项目类别:
Discovery Grants Program - Individual
Computational complexity of combinatorial problems: graph homomorphisms, packings, and good characterizations
组合问题的计算复杂性:图同态、打包和良好的表征
- 批准号:
RGPIN-2014-04760 - 财政年份:2019
- 资助金额:
$ 1.31万 - 项目类别:
Discovery Grants Program - Individual
Computational complexity of combinatorial problems: graph homomorphisms, packings, and good characterizations
组合问题的计算复杂性:图同态、打包和良好的表征
- 批准号:
RGPIN-2014-04760 - 财政年份:2018
- 资助金额:
$ 1.31万 - 项目类别:
Discovery Grants Program - Individual
Computational complexity of combinatorial problems: graph homomorphisms, packings, and good characterizations
组合问题的计算复杂性:图同态、打包和良好的表征
- 批准号:
RGPIN-2014-04760 - 财政年份:2017
- 资助金额:
$ 1.31万 - 项目类别:
Discovery Grants Program - Individual
Computational complexity of combinatorial problems: graph homomorphisms, packings, and good characterizations
组合问题的计算复杂性:图同态、打包和良好的表征
- 批准号:
RGPIN-2014-04760 - 财政年份:2016
- 资助金额:
$ 1.31万 - 项目类别:
Discovery Grants Program - Individual
Computational complexity of combinatorial problems: graph homomorphisms, packings, and good characterizations
组合问题的计算复杂性:图同态、打包和良好的表征
- 批准号:
RGPIN-2014-04760 - 财政年份:2015
- 资助金额:
$ 1.31万 - 项目类别:
Discovery Grants Program - Individual
Study of graph homomorphisms from functional analysis
从泛函分析研究图同态
- 批准号:
15K04926 - 财政年份:2015
- 资助金额:
$ 1.31万 - 项目类别:
Grant-in-Aid for Scientific Research (C)