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.

研究人员对从极值组合学和相关领域的广泛问题感兴趣。一个共同的主题是探索构建极端对象的新想法；特别是，研究者在香农容量、孤独跑步者猜想和组合差异的背景下提出了构建的新想法。在Shannon容量方面，研究者发展了一种新的奇圈幂独立集的构造，在某种意义上，它是渐近最优的。希望在这种构造中使用的代数思想能够得到进一步发展，以更深入地了解奇圈的香农容量。这位研究人员提出了一种类似的代数方法来处理一些猜想(根据R.Holzman、D.Kleitman和调查者最近的工作提出的猜想)，这些猜想涉及所谓的孤独跑步者猜想的极端对象。组合差异的研究源于Lovasz、Spencer和Vester gombi关于超图的线性差异与遗传差异之间关系的猜想。除了新的构造，这项研究还包括随机图和元胞自动机的组合学领域的问题。极值组合学中考虑的问题的形式是：位于特定离散数学系统中并满足一定条件的对象可以有多大(或多小)？对于超大型系统，我们通常对极值天体的大小感兴趣。在二十世纪，人们对这类问题的兴趣广泛增长。该领域的先驱，如Paul Erdos，在极值组合学与其他各种领域(包括计算机科学、统计物理和信息论)之间的密切联系被发现之前，就已经提出了许多这种形式的迷人问题，并设计出了解决这些问题的强大方法。香农容量是极值组合学和信息论之间重要联系的一个典型例子。香农容量给出了噪声通信信道零差错性能的度量。研究人员为一些出了名的困难信道开发了新的、接近最优的码，拟议的研究包括进一步开发这些码，目标是确定这些信道的零误差最优。细胞自动机的研究是最近极值组合学和统计物理学相互作用的一部分。元胞自动机是离散的动力系统，已被用来模拟广泛的物理现象。研究人员建议研究某些模拟晶体生长的元胞自动机的生长规律。这项工作有望对我们理解这些模型及其随机化对应模型所实现的形状产生影响。