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 过程的随机图过程中的组件结构，在该过程中，每轮都会出现一对随机边，并通过在线算法在它们之间进行选择。 在这里，我们感兴趣的是最大组件尺寸中相变的存在、时间和性质。 这里的一个主要工具是用于在随机图过程中建立浓度的微分方程方法。这项研究属于极值组合学领域。该领域考虑的问题的形式是：“一个物体可以有多大（或小）”一个特定的离散数学系统并且满足一定的条件是？ 当底层系统的大小趋于无穷大时，我们经常关注极值对象的大小的行为。 在二十世纪，人们对这些问题的兴趣广泛增长。 该领域的先驱者，例如 Paul Erd\H{o}s，甚至在极值组合学与其他各个领域（包括理论计算机科学、统计物理学）之间建立密切联系之前，就提出了许多这种形式的令人着迷的问题，并设计了解决这些问题的强大方法。和信息论）被发现。 图的香农容量是极值组合学与通信理论之间密切相互作用的经典例子。 香农容量给出了噪声通信信道的最佳零错误性能的度量，并且在信息论中非常重要。 同时，它引发了极值组合学和图论中的自然问题。 本研究项目解决了其中一些问题。