Problems in 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.