Probabilistic and Extremal Combinatorics
概率和极值组合学
基本信息
- 批准号:0701183
- 负责人:
- 金额:$ 13.79万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Continuing Grant
- 财政年份:2007
- 资助国家:美国
- 起止时间:2007-08-01 至 2010-07-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
This research project has two main parts. The first focuses on applications of the differential equations method for the analysis of greedy algorithms and random graph processes. Recent work of the investigator and Alan Frieze gives a new technique for employing this method to prove good performance of randomized algorithms on random graphs without an explicit solution (or numerical approximation of the solution) of the associated system of differential equations (the need for such often complicates application of the method). The key new idea is to use combinatorial observations to identify an invariant set in the autonomous system of ordinary differential equations that, by a standard application of the method, governs the evolution of the algorithm. Problems to be addressed in this part of the project include Hamiltonicity, matchings and 3-colorability of sparse random graphs. The second part of this research project is motivated by the problem of determining the Shannon capacities of graphs. The Shannon capacity is a function of the independence numbers of the powers of the graph. The investigator proposes a novel technique, based on combinatorial stability, for attaining upper bounds on the independence numbers of powers of odd cycles. This research is in the areas of probabilistic and extremal combinatorics. Probabilistic combinatorics is comprised of the study of random combinatorial structures, randomized algorithms and probabilistic existence proofs for combinatorics (i.e. the probabilistic method). Extremal combinatorics considers questions of the form: `How large (or small) can an object that lies in a particular discrete mathematical system and satisfies a certain condition be?' We are often concerned with the behavior of the size of the extremal objects as the size of the underlying system goes to infinity. Interest in both fields grew extensively during the twentieth century. Pioneers, such as Paul Erdos, discovered many beautiful properties of extremal and random discrete structures, posed vast arrays of fascinating questions in these areas and devised powerful methods for solving them even before the close connections between probabilistic and extremal combinatorics and various other fields (including theoretical computer science, statistical physics and information theory) were discovered. The Shannon capacities of graphs are a classic example of the close interaction between extremal combinatorics and the theory of communication. The Shannon capacity gives a measure of the optimal zero-error performance of a noisy communication channel and is centrally important in information theory. At the same time, it gives rise to natural questions in extremal combinatorics.
这个研究项目有两个主要部分。第一部分着重于微分方程方法在贪婪算法和随机图过程分析中的应用。研究者和Alan Frieze最近的工作提供了一种新技术,用于使用该方法证明随机算法在随机图上的良好性能,而不需要相关微分方程组的显式解(或解的数值近似值)(这种需要通常使该方法的应用变得复杂)。关键的新思想是使用组合观察来识别常微分方程自治系统中的不变量集,通过该方法的标准应用,控制算法的进化。这部分项目要解决的问题包括稀疏随机图的哈密性、匹配性和3色性。这个研究项目的第二部分是由确定图的香农能力的问题所激发的。香农容量是图的幂的独立数的函数。提出了一种基于组合稳定性的奇环幂独立数上界求解方法。这项研究是在概率和极值组合学领域。概率组合学是研究随机组合结构、随机算法和组合学的概率存在性证明(即概率方法)的学科。极值组合学考虑这样的问题:“在一个特定的离散数学系统中,满足一定条件的对象能有多大(或多小)?”当底层系统的大小趋于无穷大时,我们经常关注极端对象的大小的行为。在二十世纪,人们对这两个领域的兴趣都得到了广泛的发展。先驱者,如Paul Erdos,发现了极值和随机离散结构的许多美丽特性,在这些领域提出了大量有趣的问题,并设计了强大的方法来解决这些问题,甚至在概率和极值组合学与其他各种领域(包括理论计算机科学、统计物理和信息论)之间的密切联系被发现之前。图的香农能力是极值组合学与通信理论密切联系的一个经典例子。香农容量给出了噪声通信信道的最佳零误差性能的度量,在信息论中是非常重要的。同时,它也引起了极值组合中的一些自然问题。
项目成果
期刊论文数量(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 }}
Tom Bohman其他文献
Vertex Covers by Edge Disjoint Cliques
- DOI:
10.1007/s004930100017 - 发表时间:
2001-04-01 - 期刊:
- 影响因子:1.000
- 作者:
Tom Bohman;Alan Frieze;Miklós Ruszinkó;Lubos Thoma - 通讯作者:
Lubos Thoma
A critical probability for biclique partition of <em>G</em><sub><em>n</em>,<em>p</em></sub>
- DOI:
10.1016/j.jctb.2023.12.005 - 发表时间:
2024-05-01 - 期刊:
- 影响因子:
- 作者:
Tom Bohman;Jakob Hofstad - 通讯作者:
Jakob Hofstad
How many random edges make a dense graph Hamiltonian ?
有多少条随机边构成稠密图哈密顿量?
- DOI:
- 发表时间:
2001 - 期刊:
- 影响因子:0
- 作者:
Tom Bohman - 通讯作者:
Tom Bohman
Game chromatic index of graphs with given restrictions on degrees
- DOI:
10.1016/j.tcs.2008.05.026 - 发表时间:
2008-11-06 - 期刊:
- 影响因子:
- 作者:
Andrew Beveridge;Tom Bohman;Alan Frieze;Oleg Pikhurko - 通讯作者:
Oleg Pikhurko
Preventing Bullying and Sexual Harassment in Elementary Schools
防止小学欺凌和性骚扰
- DOI:
- 发表时间:
2001 - 期刊:
- 影响因子:0
- 作者:
E. Sanchez;T. Robertson;C. M. Lewis;Barri Rosenbluth;Tom Bohman;D. Casey - 通讯作者:
D. Casey
Tom Bohman的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Tom Bohman', 18)}}的其他基金
Probabilistic and Extremal Combinatorics
概率和极值组合学
- 批准号:
2246907 - 财政年份:2023
- 资助金额:
$ 13.79万 - 项目类别:
Continuing Grant
Conference: 21st International Conference on Random Structures & Algorithms
会议:第21届国际随机结构会议
- 批准号:
2309068 - 财政年份:2023
- 资助金额:
$ 13.79万 - 项目类别:
Standard Grant
17th International Conference on Random Structures and Algorithms
第十七届随机结构与算法国际会议
- 批准号:
1506338 - 财政年份:2015
- 资助金额:
$ 13.79万 - 项目类别:
Standard Grant
Extremal and Probabilistic Combinatorics via Regularity and Graph Limits
通过正则性和图极限的极值和概率组合
- 批准号:
1100215 - 财政年份:2011
- 资助金额:
$ 13.79万 - 项目类别:
Standard Grant
Probabilistic and Extremal Combinatorics
概率和极值组合学
- 批准号:
1001638 - 财政年份:2010
- 资助金额:
$ 13.79万 - 项目类别:
Continuing Grant
Mathematical Sciences Postdoctoral Research Fellowships
数学科学博士后研究奖学金
- 批准号:
9627408 - 财政年份:1996
- 资助金额:
$ 13.79万 - 项目类别:
Fellowship Award
相似国自然基金
带奇点的extremal度量和toric流形上的extremal度量
- 批准号:10901160
- 批准年份:2009
- 资助金额:10.0 万元
- 项目类别:青年科学基金项目
相似海外基金
Probabilistic and Extremal Combinatorics
概率和极值组合学
- 批准号:
2246907 - 财政年份:2023
- 资助金额:
$ 13.79万 - 项目类别:
Continuing Grant
CAREER: Problems in Extremal and Probabilistic Combinatorics
职业:极值和概率组合问题
- 批准号:
2146406 - 财政年份:2022
- 资助金额:
$ 13.79万 - 项目类别:
Continuing Grant
Algebraic and Probabilistic Methods in Extremal Combinatorics
极值组合中的代数和概率方法
- 批准号:
2100157 - 财政年份:2020
- 资助金额:
$ 13.79万 - 项目类别:
Standard Grant
Applications of probabilistic combinatorics and extremal set theory to deriving bounds in classical and quantum coding theory
概率组合学和极值集合论在经典和量子编码理论中推导界限的应用
- 批准号:
20K11668 - 财政年份:2020
- 资助金额:
$ 13.79万 - 项目类别:
Grant-in-Aid for Scientific Research (C)
Algebraic and Probabilistic Methods in Extremal Combinatorics
极值组合中的代数和概率方法
- 批准号:
1953772 - 财政年份:2020
- 资助金额:
$ 13.79万 - 项目类别:
Standard Grant
Extremal Combinatorics, Probabilistic Combinatorics
极值组合学、概率组合学
- 批准号:
2281342 - 财政年份:2019
- 资助金额:
$ 13.79万 - 项目类别:
Studentship
Topics in Extremal and Probabilistic Combinatorics via the study of uniform probability spaces with weak dependencies
通过研究具有弱依赖性的均匀概率空间来研究极值和概率组合学主题
- 批准号:
1810272 - 财政年份:2016
- 资助金额:
$ 13.79万 - 项目类别:
Studentship
Probabilistic and Extremal Combinatorics
概率和极值组合学
- 批准号:
1600742 - 财政年份:2016
- 资助金额:
$ 13.79万 - 项目类别:
Continuing Grant