Problems in Extremal Combinatorics

极值组合问题

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

This project has two parts: an investigation of the independence numbers of the powers of fixed graphsand a study of the emergence of a giant component in `guided' versions of the classical random graph. The first part is motivated by the many open questions regarding the Shannon capacities of graphs and focuses on the possible behaviors of the sequence given by the independence numbers of the powers of a fixed graph. The odd cycles and their complements are particularlyimportant examples and play a central role in this partof the project. While a wide range of techniques -- including algebraic methods -- may be useful here, recent progress has come through the interplay of novel constructions for, and structural conditions imposed onlarge independent sets in these graph powers. In the second part of this project we study the component structure in the random graph processes known as Achlioptas processes, processes in which a pair of random edges is presented in each round and an on-linealgorithm chooses between them. Here we are interested in the existence, timing and nature of a phase transition in the size of the largest component. A principle tool here is the differential equations method for establishing concentration in random graph processes.This research is in the area of extremal combinatorics.Questions considered in this field are of the form: `How large (or small) can an object that lies in a particulardiscrete mathematical system and satisfies a certain condition be?' We are often concerned with the behavior of the size of the extremal objects as the size of the underlying system goes to infinity. Interest in such questions grew extensively during the twentieth century. Pioneers of the field, such as Paul Erd\H{o}s, posed many fascinating questions of this form and devised powerful methods for solving them even before the close connections between extremal combinatorics and various other fields (including theoretical computer science, statistical physics and information theory) were discovered. The Shannon capacities of graphs are a classic example of the close interaction between extremal combinatorics and the theory of communication. The Shannon capacity gives a measure of the optimal zero-error performance of a noisy communication channel and is centrally important in information theory. At the same time, it gives rise to natural questions in extremal combinatorics and graph theory. Some of thesequestions are addressed in this research project.

该项目有两个部分：研究固定图的力量的独立性数量，并研究了经典随机图的“指导”版本中巨型组件的出现。 第一部分是由有关图表的香农能力的许多开放问题激发的，并着重于固定图的幂的独立性数字给出的顺序的可能行为。 奇怪的周期及其补充特别重要的例子，在该项目的这一部分中起着核心作用。 尽管在这里可能有用的多种技术（包括代数方法）可能很有用，但最近的进展是通过新颖的构造的相互作用以及在这些图形幂中施加独立集合的结构条件。 在该项目的第二部分中，我们研究了被称为ACHLIOPTAS过程的随机图过程中的组件结构，其中每轮介绍了一对随机边缘，并且在它们之间选择了一对随机边缘。 在这里，我们对最大成分大小的相变的存在，时机和性质感兴趣。 这里的原理工具是在随机图过程中建立浓度的微分方程方法。这项研究位于极端组合区域。在此领域中考虑的问题的形式是：“````````````````````````````````````````````````````````````````````````````````````` 我们经常关注极端物体的大小的行为，因为基础系统的大小输入无穷大。 在20世纪，对这些问题的兴趣广泛增长。 该领域的开拓者，例如Paul Erd \ H {O}，提出了许多令人着迷的问题，并设计了有力的方法，即使在极端组合和其他各个领域之间的密切联系之前，也发现了解决方案的强大方法（包括理论计算机科学，统计学物理学和信息理论）。 图形的香农能力是极端组合学与交流理论之间紧密相互作用的经典示例。 香农的能力衡量了嘈杂的通信渠道的最佳零错误性能，并且在信息理论中非常重要。 同时，它引起了极端组合和图理论的自然问题。 该研究项目解决了其中的一些问题。