Probabilistic and Extremal Combinatorics
概率和极值组合学
基本信息
- 批准号:2246907
- 负责人:
- 金额:$ 24万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Continuing Grant
- 财政年份:2023
- 资助国家:美国
- 起止时间:2023-08-01 至 2026-07-31
- 项目状态:未结题
- 来源:
- 关键词:
项目摘要
This research project is an investigation of discrete mathematical objects like networks and codes. Extremal combinatorics is focused on developing a better understanding of discrete mathematical objects that optimize interesting or desirable properties, while probabilistic combinatorics studies discrete mathematical objects that are generated by a series of random choices. These two research directions are intimately related as randomized algorithms are a remarkably powerful tool for the construction of interesting discrete mathematical objects. Furthermore, randomness is a major theme of the work on extremal problems for discrete structures as a deep understanding of the ways in which deterministic objects mimic their randomized counterparts often leads to major progress. This research has the potential to benefit society through the development of new algorithms for computational problems on large networks, new methods for analyzing existing network algorithms, and new codes and communication protocols. The project also provides training opportunities at both the undergraduate and graduate level.This research is in the broad areas of probabilistic and extremal combinatorics. The work in probabilistic combinatorics is focused on very sharp concentration of global parameters of the binomial random graph and problems regarding the decomposition of the edge set of the uniform random graph into cliques or bicliques. The work on sharp concentration in the binomial random graph is motivated by a recent result of the investigator and a doctoral student that establishes 2-point concentration of the independence number of the binomial random graph over a broad range of the probability parameter. The comprehensive understanding of the extent of concentration of the independence number of the binomial random graph is one of the goals of this part of the research program. This project also includes further study of the fascinating lonely runner conjecture and some problems on Ramsey numbers for hypergraphs and posets. While the structures that we consider in these two contexts are not necessarily random, we expect the interplay of structure and randomness (i.e. pseudorandom properties of discrete structures) to play a major role. The ultimate goal of this research is to find new methods that are broadly applicable in discrete mathematics.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.
本研究项目是对离散数学对象(如网络和代码)的研究。极值组合学专注于更好地理解离散数学对象,优化有趣或理想的属性,而概率组合学研究由一系列随机选择生成的离散数学对象。这两个研究方向是密切相关的随机算法是一个非常强大的工具,为建设有趣的离散数学对象。此外,随机性是离散结构极值问题工作的一个主要主题,因为对确定性对象模仿随机对象的方式的深入理解往往会导致重大进展。这项研究有可能通过开发大型网络计算问题的新算法,分析现有网络算法的新方法以及新的代码和通信协议来造福社会。该项目还提供了本科生和研究生的培训机会。这项研究是在概率和极值组合学的广泛领域。在概率组合学的工作集中在非常尖锐的浓度的全球参数的二项式随机图和问题的分解的边缘集的均匀随机图成团或bicliques。在二项式随机图中的浓度急剧的工作是由最近的结果的调查员和一个博士生,建立2点浓度的独立数的二项式随机图在广泛的概率参数。全面了解二项随机图的独立数的集中程度是这部分研究计划的目标之一。本项目还包括对有趣的孤独跑步者猜想的进一步研究以及超图和偏序集的Ramsey数的一些问题。虽然我们在这两个上下文中考虑的结构不一定是随机的,但我们希望结构和随机性(即离散结构的伪随机特性)的相互作用发挥主要作用。该研究的最终目标是找到广泛适用于离散数学的新方法。该奖项反映了NSF的法定使命,并通过使用基金会的知识价值和更广泛的影响审查标准进行评估,被认为值得支持。
项目成果
期刊论文数量(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)}}的其他基金
Conference: 21st International Conference on Random Structures & Algorithms
会议:第21届国际随机结构会议
- 批准号:
2309068 - 财政年份:2023
- 资助金额:
$ 24万 - 项目类别:
Standard Grant
17th International Conference on Random Structures and Algorithms
第十七届随机结构与算法国际会议
- 批准号:
1506338 - 财政年份:2015
- 资助金额:
$ 24万 - 项目类别:
Standard Grant
Extremal and Probabilistic Combinatorics via Regularity and Graph Limits
通过正则性和图极限的极值和概率组合
- 批准号:
1100215 - 财政年份:2011
- 资助金额:
$ 24万 - 项目类别:
Standard Grant
Probabilistic and Extremal Combinatorics
概率和极值组合学
- 批准号:
1001638 - 财政年份:2010
- 资助金额:
$ 24万 - 项目类别:
Continuing Grant
Probabilistic and Extremal Combinatorics
概率和极值组合学
- 批准号:
0701183 - 财政年份:2007
- 资助金额:
$ 24万 - 项目类别:
Continuing Grant
Mathematical Sciences Postdoctoral Research Fellowships
数学科学博士后研究奖学金
- 批准号:
9627408 - 财政年份:1996
- 资助金额:
$ 24万 - 项目类别:
Fellowship Award
相似国自然基金
带奇点的extremal度量和toric流形上的extremal度量
- 批准号:10901160
- 批准年份:2009
- 资助金额:10.0 万元
- 项目类别:青年科学基金项目
相似海外基金
CAREER: Problems in Extremal and Probabilistic Combinatorics
职业:极值和概率组合问题
- 批准号:
2146406 - 财政年份:2022
- 资助金额:
$ 24万 - 项目类别:
Continuing Grant
Algebraic and Probabilistic Methods in Extremal Combinatorics
极值组合中的代数和概率方法
- 批准号:
2100157 - 财政年份:2020
- 资助金额:
$ 24万 - 项目类别:
Standard Grant
Applications of probabilistic combinatorics and extremal set theory to deriving bounds in classical and quantum coding theory
概率组合学和极值集合论在经典和量子编码理论中推导界限的应用
- 批准号:
20K11668 - 财政年份:2020
- 资助金额:
$ 24万 - 项目类别:
Grant-in-Aid for Scientific Research (C)
Algebraic and Probabilistic Methods in Extremal Combinatorics
极值组合中的代数和概率方法
- 批准号:
1953772 - 财政年份:2020
- 资助金额:
$ 24万 - 项目类别:
Standard Grant
Extremal Combinatorics, Probabilistic Combinatorics
极值组合学、概率组合学
- 批准号:
2281342 - 财政年份:2019
- 资助金额:
$ 24万 - 项目类别:
Studentship
Topics in Extremal and Probabilistic Combinatorics via the study of uniform probability spaces with weak dependencies
通过研究具有弱依赖性的均匀概率空间来研究极值和概率组合学主题
- 批准号:
1810272 - 财政年份:2016
- 资助金额:
$ 24万 - 项目类别:
Studentship
Probabilistic and Extremal Combinatorics
概率和极值组合学
- 批准号:
1600742 - 财政年份:2016
- 资助金额:
$ 24万 - 项目类别:
Continuing Grant
Extremal and Probabilistic Combinatorics with Applications
极值和概率组合学及其应用
- 批准号:
1600811 - 财政年份:2016
- 资助金额:
$ 24万 - 项目类别:
Standard Grant