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.

这个项目包括两个部分：一个是关于固定图的幂的独立数的调查，另一个是关于经典随机图的“有向导”版本中出现一个巨型分量的研究。第一部分是由许多关于图的Shannon容量的公开问题引起的，并集中于由固定图的幂的独立数给出的序列的可能行为。奇数周期和它们的补充是特别重要的例子，在项目的这一部分中发挥着核心作用。虽然许多技术--包括代数方法--在这里可能是有用的，但最近的进展是通过这些图的幂中的大的独立集的新颖构造和施加在其上的结构条件的相互作用而来的。在这个项目的第二部分，我们研究了称为Achlioptas过程的随机图过程的分量结构，即在每一轮中呈现一对随机边并在它们之间进行选择的在线算法的过程。在这里，我们感兴趣的是最大分量大小的相变的存在、时间和性质。这里的一个主要工具是在随机图过程中建立集中度的微分方程式方法。这项研究是在极值组合学领域进行的。这一领域考虑的问题是这样的：位于特定离散数学系统中并满足一定条件的对象能有多大(或多小)？随着底层系统的大小变得无限大，我们经常关心极端物体的大小行为。在二十世纪，人们对这类问题的兴趣广泛增长。在极值组合学与其他领域(包括理论计算机科学、统计物理和信息论)之间的密切联系被发现之前，该领域的先驱，如保罗·埃德·S，就提出了许多有趣的问题，并设计了强有力的方法来解决这些问题。图的Shannon容量是极值组合学与传播学之间密切互动的经典例子。香农容量给出了噪声通信信道的最佳零差错性能的度量，并且在信息论中具有重要意义。同时，它也引发了极值组合学和图论中的自然问题。其中一些问题在本研究项目中得到了解决。