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.
研究者对极值组合学和相关领域的广泛问题感兴趣。 一个共同的主题是探索新的想法建设的极端对象,特别是,调查人员提出了新的想法建设的设置香农容量,孤独的亚军猜想,和组合的差异。 在香农容量领域,研究者已经开发出一种新的构造独立集的幂的奇循环,这是在某种意义上,渐近最优的。 人们希望,在这个建设中使用的代数思想可以进一步发展,让更多的洞察奇循环的香农容量。 研究人员建议一个类似的代数方法,以一些代数(代数,遵循最近的工作R。Holzman,D. Kleitman和调查员)关于极端对象的所谓孤独的跑步者猜想。 组合差异的研究是由Lovasz,Spencer和Vestergombi关于超图的线性差异与遗传差异之间关系的一个猜想激发的。 除了新的建设工作,这项研究包括在随机图和组合领域的细胞automata.Questions考虑极值组合的形式:“多大(或小)可以是一个对象,位于一个特定的离散数学系统,并满足一定的条件?“我们通常对非常大的系统的极端物体的大小感兴趣。 在二十世纪,人们对这些问题的兴趣广泛增长。 这一领域的先驱,如保罗·埃尔德什(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
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