Extremal Combinatorics

极值组合学

基本信息

  • 批准号:
    0100400
  • 负责人:
  • 金额:
    $ 9.17万
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Continuing Grant
  • 财政年份:
    2001
  • 资助国家:
    美国
  • 起止时间:
    2001-07-01 至 2004-06-30
  • 项目状态:
    已结题

项目摘要

The investigator is interested in a wide range of questions from extremal combinatorics and related fields. A common theme is the exploration of new ideas for the construction of extremal objects; in particular, the investigator suggests new ideas for constructions in the settings of Shannon capacity, the lonely runner conjecture, and combinatorial discrepancy. In the area of Shannon capacity, the investigator has developed a new construction for independent sets in the powers of odd cycles that is, in a sense, asymptotically optimal. It is hoped that the algebraic ideas used in this construction can be further developed to give more insight into the Shannon capacities of odd cycles. The investigator suggests a similar algebraic approach to a number of conjectures (conjectures that follow from recent work of R. Holzman, D. Kleitman and the investigator) concerning the extremal objects for the so-called lonely runner conjecture. The research on combinatorial discrepancy is motivated by a conjecture of Lovasz, Spencer and Vestergombi on the relationship between the linear discrepancy and hereditary discrepancy of a hypergraph. In addition to work on new constructions, this research includes questions in the fields of random graphs and the combinatorics of cellular automata.Questions considered in extremal combinatorics are 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 usually interested in the size of extremal objects for very large systems. Interest in such questions grew extensively during the twentieth century. Pioneers of the field, such as Paul Erdos, had posed many fascinating questions of this form and had devised powerful methods for solving them even before the close connections between extremal combinatorics and various other fields (including computer science, statistical physics and information theory) had been discovered. Shannon capacity is a prime example of the significant link between extremal combinatorics and information theory. Shannon capacity gives a measure of the zero-error performance of a noisy communications channel. The investigator has developed new, near--optimal codes for some notoriously difficult channels, and the proposed research includes further development of these codes with the goal of determining the zero-error optimum of these channels. The study of cellular automata has been part of the recent interaction between extremal combinatorics and statistical physics. Cellular automata are discrete dynamical systems that have been used to model a wide range of physical phenomena. The investigator proposes research on the regularity of growth of certain cellular automata that model crystal growth. This work is expected to have impact on our understanding of the shapes achieved by these models and their randomized counterparts.
研究人员对从极值组合学和相关领域的广泛问题感兴趣。一个共同的主题是探索构建极端对象的新想法;特别是,研究者在香农容量、孤独跑步者猜想和组合差异的背景下提出了构建的新想法。在Shannon容量方面,研究者发展了一种新的奇圈幂独立集的构造,在某种意义上,它是渐近最优的。希望在这种构造中使用的代数思想能够得到进一步发展,以更深入地了解奇圈的香农容量。这位研究人员提出了一种类似的代数方法来处理一些猜想(根据R.Holzman、D.Kleitman和调查者最近的工作提出的猜想),这些猜想涉及所谓的孤独跑步者猜想的极端对象。组合差异的研究源于Lovasz、Spencer和Vester gombi关于超图的线性差异与遗传差异之间关系的猜想。除了新的构造,这项研究还包括随机图和元胞自动机的组合学领域的问题。极值组合学中考虑的问题的形式是:位于特定离散数学系统中并满足一定条件的对象可以有多大(或多小)?对于超大型系统,我们通常对极值天体的大小感兴趣。在二十世纪,人们对这类问题的兴趣广泛增长。该领域的先驱,如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
  • 资助金额:
    $ 9.17万
  • 项目类别:
    Continuing Grant
Conference: 21st International Conference on Random Structures & Algorithms
会议:第21届国际随机结构会议
  • 批准号:
    2309068
  • 财政年份:
    2023
  • 资助金额:
    $ 9.17万
  • 项目类别:
    Standard Grant
17th International Conference on Random Structures and Algorithms
第十七届随机结构与算法国际会议
  • 批准号:
    1506338
  • 财政年份:
    2015
  • 资助金额:
    $ 9.17万
  • 项目类别:
    Standard Grant
Extremal and Probabilistic Combinatorics via Regularity and Graph Limits
通过正则性和图极限的极值和概率组合
  • 批准号:
    1100215
  • 财政年份:
    2011
  • 资助金额:
    $ 9.17万
  • 项目类别:
    Standard Grant
Probabilistic and Extremal Combinatorics
概率和极值组合学
  • 批准号:
    1001638
  • 财政年份:
    2010
  • 资助金额:
    $ 9.17万
  • 项目类别:
    Continuing Grant
Probabilistic and Extremal Combinatorics
概率和极值组合学
  • 批准号:
    0701183
  • 财政年份:
    2007
  • 资助金额:
    $ 9.17万
  • 项目类别:
    Continuing Grant
Problems in Extremal Combinatorics
极值组合问题
  • 批准号:
    0401147
  • 财政年份:
    2004
  • 资助金额:
    $ 9.17万
  • 项目类别:
    Standard Grant
Mathematical Sciences Postdoctoral Research Fellowships
数学科学博士后研究奖学金
  • 批准号:
    9627408
  • 财政年份:
    1996
  • 资助金额:
    $ 9.17万
  • 项目类别:
    Fellowship Award

相似海外基金

Extremal Combinatorics: Themes and Challenging Problems
极值组合学:主题和挑战性问题
  • 批准号:
    2401414
  • 财政年份:
    2023
  • 资助金额:
    $ 9.17万
  • 项目类别:
    Continuing Grant
Discrete Geometry and Extremal Combinatorics
离散几何和极值组合
  • 批准号:
    2246659
  • 财政年份:
    2023
  • 资助金额:
    $ 9.17万
  • 项目类别:
    Standard Grant
Extremal Combinatorics: Themes and Challenging Problems
极值组合学:主题和挑战性问题
  • 批准号:
    2246641
  • 财政年份:
    2023
  • 资助金额:
    $ 9.17万
  • 项目类别:
    Continuing Grant
Probabilistic and Extremal Combinatorics
概率和极值组合学
  • 批准号:
    2246907
  • 财政年份:
    2023
  • 资助金额:
    $ 9.17万
  • 项目类别:
    Continuing Grant
Extremal Combinatorics Exact Bounds
极值组合精确界
  • 批准号:
    574168-2022
  • 财政年份:
    2022
  • 资助金额:
    $ 9.17万
  • 项目类别:
    University Undergraduate Student Research Awards
FRG: Collaborative Research: Extremal Combinatorics and Flag Algebras
FRG:协作研究:极值组合学和标志代数
  • 批准号:
    2152488
  • 财政年份:
    2022
  • 资助金额:
    $ 9.17万
  • 项目类别:
    Standard Grant
Extremal Combinatorics Asymptotics
极值组合渐近学
  • 批准号:
    574167-2022
  • 财政年份:
    2022
  • 资助金额:
    $ 9.17万
  • 项目类别:
    University Undergraduate Student Research Awards
Extremal Combinatorics: Problems and Algorithmic Aspects
极值组合学:问题和算法方面
  • 批准号:
    2154082
  • 财政年份:
    2022
  • 资助金额:
    $ 9.17万
  • 项目类别:
    Continuing Grant
Graph Theory and Extremal Combinatorics
图论和极值组合学
  • 批准号:
    576024-2022
  • 财政年份:
    2022
  • 资助金额:
    $ 9.17万
  • 项目类别:
    Alexander Graham Bell Canada Graduate Scholarships - Master's
FRG: Collaborative Research: Extremal Combinatorics and Flag Algebras
FRG:协作研究:极值组合学和标志代数
  • 批准号:
    2152490
  • 财政年份:
    2022
  • 资助金额:
    $ 9.17万
  • 项目类别:
    Standard Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了