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 对超图的线性差异和遗传差异之间关系的猜想。 除了新结构的工作之外，这项研究还包括随机图和元胞自动机组合领域的问题。极值组合学中考虑的问题具有以下形式：“位于特定位置的物体可以有多大（或有多小）”离散数学系统并且满足一定的条件是？ 我们通常对非常大的系统的极值对象的大小感兴趣。 在二十世纪，人们对这些问题的兴趣广泛增长。 该领域的先驱，例如保罗·埃尔多斯（Paul Erdos），甚至在极值组合学与其他各个领域（包括计算机科学、统计物理学和信息论）之间的密切联系出现之前，就提出了许多这种形式的令人着迷的问题，并设计了解决这些问题的强大方法。被发现了。 香农容量是极值组合学和信息论之间重要联系的一个典型例子。 香农容量给出了噪声通信信道的零错误性能的度量。 研究人员为一些众所周知的困难通道开发了新的、接近最优的代码，并且拟议的研究包括进一步开发这些代码，目的是确定这些通道的零误差最优值。 元胞自动机的研究是极值组合学和统计物理学最近相互作用的一部分。 元胞自动机是离散动力系统，已用于模拟各种物理现象。 研究人员建议研究模拟晶体生长的某些元胞自动机的生长规律。 这项工作预计将影响我们对这些模型及其随机对应模型所实现的形状的理解。