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的猜想引起的，该研究是关于线性差异与超图的遗传性差异之间关系的。 除了从事新结构的工作外，这项研究还包括随机图和蜂窝自动机的组合的问题。极端组合学中考虑的问题的形式是：`````````` 我们通常对非常大系统的极端物体的大小感兴趣。 在20世纪，对这些问题的兴趣广泛增长。 该领域的先驱，例如保罗·埃尔多斯（Paul Erdos），提出了许多令人着迷的这种形式的问题，并设计了有力的方法来解决它们，甚至在发现了极端组合和其他各个领域（包括计算机科学，统计物理学和信息理论）之间的密切联系之前就解决了这些形式。 香农能力是极端组合学与信息理论之间重要联系的一个主要例子。 香农的容量衡量了嘈杂的通信渠道的零错误性能。 研究人员为一些臭名昭著的渠道开发了新的，近乎最佳的代码，拟议的研究包括进一步开发这些代码，目的是确定这些渠道的零错误最佳。 细胞自动机的研究已成为极端组合和统计物理学之间最近相互作用的一部分。 细胞自动机是离散的动力系统，用于对广泛的物理现象进行建模。 研究者提出了对某些细胞自动机的生长的规律性研究，以模拟晶体生长。 预计这项工作会影响我们对这些模型及其随机同行所达到的形状的理解。