Extremal Combinatorics

极值组合学

• 批准号: 0100400
• 负责人: Tom Bohman
• 金额: $ 9.17万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-07-01 至 2004-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0100400&HistoricalAwards=false
• 关键词: Extremal; Combinatorics

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），提出了许多这种形式的迷人问题，甚至在极值组合学与其他各种领域（包括计算机科学、统计物理和信息论）之间的密切联系被发现之前，就已经设计出了解决这些问题的强大方法。 香农容量是极值组合学和信息论之间重要联系的一个主要例子。 香农容量给出了噪声通信信道的零差错性能的度量。 研究人员已经开发出新的，近-最佳的代码，一些臭名昭著的困难的渠道，和拟议的研究包括进一步发展这些代码的目标是确定这些渠道的零误差最佳。 元胞自动机的研究是极值组合学和统计物理学之间最近相互作用的一部分。 元胞自动机是离散的动力系统，已被用来模拟广泛的物理现象。 研究者提出研究某些模拟晶体生长的元胞自动机的生长规律。 这项工作预计将对我们理解这些模型及其随机对应物所实现的形状产生影响。