Probabilistic and Extremal Combinatorics

概率和极值组合学

基本信息

  • 批准号:
    1001638
  • 负责人:
  • 金额:
    $ 27万
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Continuing Grant
  • 财政年份:
    2010
  • 资助国家:
    美国
  • 起止时间:
    2010-08-01 至 2013-07-31
  • 项目状态:
    已结题

项目摘要

The majority of this research is in the area of probabilistic combinatorics, which is comprised of the study of random combinatorial structures, randomized algorithms and probabilistic existence proofs for combinatorics (i.e. the probabilistic method). In recent years, this field has seen the development of a technique for proving that key statistics of a discrete stochastic process are likely to remain close to their expected trajectories as the process evolves. This method is known as the differential equations method for greedy algorithms and random graph processes. The investigator recently extended this technique to analyze the triangle-free process, a `controlled' random graph process that produces an interesting distribution on the space of triangle-free graphs. The investigator showed that a graph drawn from this distribution is likely to have independence number within a constant multiplicative factor of the smallest possible. In other words, the triangle-free process produces a Ramsey R(3,t) graph. The investigator shall continue the development of this method for the study of related `controlled' random processes, with an emphasis on processes that are interesting from the perspective of extremal combinatorics. Related questions are motivated by computer science. Here the investigator attempts to develop applications of the differential equations method to prove good performance of randomized algorithms without an explicit solution, or numerical approximation of the solution, of the associated differential equation (the need for such information often significantly complicates application of this method).This research project is an investigation of discrete mathematical objects, like networks or codes, whose evolution over time is determined by a sequence of random choices. We are particularly interested in processes where there is dependence between the choices made in different rounds. While such processes can be good models for the dynamics of real-world phenomenon, like the spread of a disease in a network or phase transitions in materials, the focus of this research is on processes that generate interesting mathematical objects. Randomness has long played an important role in the construction of sophisticated combinatorial objects, just as randomness plays an a central role in many algorithms in computer science. This research is expected to have an impact in multiple domains as the investigator shall develop general tools for understanding the evolution of these systems over time.
该研究的大部分是在概率组合学领域,其中包括随机组合结构,随机算法和组合的概率存在性证明(即概率方法)的研究。 近年来,这一领域已经看到了一种技术的发展,用于证明离散随机过程的关键统计数据可能会保持接近其预期的轨迹,随着过程的演变。 这种方法被称为贪婪算法和随机图过程的微分方程方法。 研究人员最近扩展了这种技术来分析三角形自由的过程,一个“控制”的随机图形过程,产生一个有趣的分布在空间上的三角形自由图。 研究人员表明,从这个分布绘制的图可能在最小可能的常数乘法因子内具有独立数。 换句话说,无三角形过程产生Ramsey R(3,t)图。 研究者应继续开发这种方法来研究相关的“受控”随机过程,重点是从极端组合学的角度来看有趣的过程。 相关问题的动机是计算机科学。 在这里,研究者试图发展微分方程方法的应用,以证明随机算法的良好性能,而无需相关微分方程的显式解或解的数值近似(对这些信息的需要通常使这种方法的应用显着复杂化)。这个研究项目是对离散数学对象的调查,如网络或代码,其随时间的演变由一系列随机选择决定。 我们特别感兴趣的过程中,有在不同回合的选择之间的依赖性。 虽然这样的过程可以很好地模拟真实世界现象的动态,比如疾病在网络中的传播或材料中的相变,但这项研究的重点是生成有趣的数学对象的过程。 长期以来,随机性在复杂组合对象的构建中扮演着重要角色,就像随机性在计算机科学中的许多算法中扮演着核心角色一样。 这项研究预计将在多个领域产生影响,因为研究人员将开发通用工具来了解这些系统随时间的演变。

项目成果

期刊论文数量(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
  • 资助金额:
    $ 27万
  • 项目类别:
    Continuing Grant
Conference: 21st International Conference on Random Structures & Algorithms
会议:第21届国际随机结构会议
  • 批准号:
    2309068
  • 财政年份:
    2023
  • 资助金额:
    $ 27万
  • 项目类别:
    Standard Grant
17th International Conference on Random Structures and Algorithms
第十七届随机结构与算法国际会议
  • 批准号:
    1506338
  • 财政年份:
    2015
  • 资助金额:
    $ 27万
  • 项目类别:
    Standard Grant
Extremal and Probabilistic Combinatorics via Regularity and Graph Limits
通过正则性和图极限的极值和概率组合
  • 批准号:
    1100215
  • 财政年份:
    2011
  • 资助金额:
    $ 27万
  • 项目类别:
    Standard Grant
Probabilistic and Extremal Combinatorics
概率和极值组合学
  • 批准号:
    0701183
  • 财政年份:
    2007
  • 资助金额:
    $ 27万
  • 项目类别:
    Continuing Grant
Problems in Extremal Combinatorics
极值组合问题
  • 批准号:
    0401147
  • 财政年份:
    2004
  • 资助金额:
    $ 27万
  • 项目类别:
    Standard Grant
Extremal Combinatorics
极值组合学
  • 批准号:
    0100400
  • 财政年份:
    2001
  • 资助金额:
    $ 27万
  • 项目类别:
    Continuing Grant
Mathematical Sciences Postdoctoral Research Fellowships
数学科学博士后研究奖学金
  • 批准号:
    9627408
  • 财政年份:
    1996
  • 资助金额:
    $ 27万
  • 项目类别:
    Fellowship Award

相似国自然基金

带奇点的extremal度量和toric流形上的extremal度量
  • 批准号:
    10901160
  • 批准年份:
    2009
  • 资助金额:
    10.0 万元
  • 项目类别:
    青年科学基金项目

相似海外基金

Probabilistic and Extremal Combinatorics
概率和极值组合学
  • 批准号:
    2246907
  • 财政年份:
    2023
  • 资助金额:
    $ 27万
  • 项目类别:
    Continuing Grant
CAREER: Problems in Extremal and Probabilistic Combinatorics
职业:极值和概率组合问题
  • 批准号:
    2146406
  • 财政年份:
    2022
  • 资助金额:
    $ 27万
  • 项目类别:
    Continuing Grant
Extremal and Probabilistic Combinatorics
极值和概率组合学
  • 批准号:
    2763343
  • 财政年份:
    2022
  • 资助金额:
    $ 27万
  • 项目类别:
    Studentship
Algebraic and Probabilistic Methods in Extremal Combinatorics
极值组合中的代数和概率方法
  • 批准号:
    2100157
  • 财政年份:
    2020
  • 资助金额:
    $ 27万
  • 项目类别:
    Standard Grant
Applications of probabilistic combinatorics and extremal set theory to deriving bounds in classical and quantum coding theory
概率组合学和极值集合论在经典和量子编码理论中推导界限的应用
  • 批准号:
    20K11668
  • 财政年份:
    2020
  • 资助金额:
    $ 27万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
Algebraic and Probabilistic Methods in Extremal Combinatorics
极值组合中的代数和概率方法
  • 批准号:
    1953772
  • 财政年份:
    2020
  • 资助金额:
    $ 27万
  • 项目类别:
    Standard Grant
Extremal Combinatorics, Probabilistic Combinatorics
极值组合学、概率组合学
  • 批准号:
    2281342
  • 财政年份:
    2019
  • 资助金额:
    $ 27万
  • 项目类别:
    Studentship
Extremal and probabilistic combinatorics
极值和概率组合学
  • 批准号:
    2140269
  • 财政年份:
    2018
  • 资助金额:
    $ 27万
  • 项目类别:
    Studentship
Topics in Extremal and Probabilistic Combinatorics via the study of uniform probability spaces with weak dependencies
通过研究具有弱依赖性的均匀概率空间来研究极值和概率组合学主题
  • 批准号:
    1810272
  • 财政年份:
    2016
  • 资助金额:
    $ 27万
  • 项目类别:
    Studentship
Probabilistic and Extremal Combinatorics
概率和极值组合学
  • 批准号:
    1600742
  • 财政年份:
    2016
  • 资助金额:
    $ 27万
  • 项目类别:
    Continuing Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了