Problems in Extremal Combinatorics

该项目有两个部分：一个调查的独立数的权力固定图和一个研究的出现一个巨大的组件在'引导'版本的经典随机图。 第一部分的动机是许多开放的问题，关于图的香农容量，并专注于一个固定的图的权力的独立数所给出的序列的可能的行为。 奇循环和它们的补集是特别重要的例子，在这个项目的这一部分中起着中心作用。 虽然广泛的技术-包括代数方法-可能是有用的，在这里，最近的进展已经通过新的建设的相互作用，和结构条件强加于大型独立集在这些图形的权力。 在这个项目的第二部分中，我们研究了被称为Achlioptas过程的随机图过程中的组件结构，在该过程中，一对随机边在每一轮中呈现，并且在线算法在它们之间进行选择。 在这里，我们感兴趣的是在最大组件的大小相变的存在，时间和性质。 这里的一个主要工具是微分方程方法建立浓度在随机图过程。这项研究是在该地区的极值组合。在这一领域考虑的问题的形式：“多大（或小）可以是一个对象，位于一个特定的离散数学系统，并满足一定的条件？“我们经常关注极端物体的大小的行为，因为底层系统的大小趋于无穷大。 在二十世纪，人们对这些问题的兴趣广泛增长。 该领域的先驱，如保罗·厄尔德·霍斯，提出了许多这种形式的迷人问题，并设计了强大的方法来解决它们，甚至在极值组合学和其他各种领域（包括理论计算机科学，统计物理和信息论）之间的密切联系被发现之前。 图的香农容量是极值组合学和通信理论之间密切相互作用的一个经典例子。 香农容量给出了噪声通信信道的最佳零错误性能的度量，并且在信息论中非常重要。 与此同时，它引起了极值组合学和图论中的自然问题。 其中一些问题在本研究项目中得到了解决。

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.