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.
该研究项目有两个主要部分。第一个重点是应用微分方程方法分析贪婪算法和随机图过程。 最近的工作的调查员和艾伦弗里兹提供了一种新的技术,采用这种方法来证明良好的性能随机算法的随机图没有显式的解决方案(或数值近似的解决方案)的相关系统的微分方程(需要这样往往复杂的应用程序的方法)。 关键的新思想是使用组合观测来确定常微分方程自治系统中的不变集,通过该方法的标准应用,管理算法的演变。 在这部分的项目中要解决的问题包括稀疏随机图的哈密尔顿性,匹配和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 }}
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














{{item.name}}会员




