Probabilistic Methods in Graph Theory

点击翻译按钮获取中文摘要

Graph theory is a dynamic field in both theory and applications. Graphs consist of a set of vertices and a set of edges connecting some pairs of these vertices . Many problems of practical importance can be modelled using graphs: for instance a network of cities (which are represented by vertices) and connections between them give rise to weighted graph. The well known travelling salesman problem then asks for the shortest tour which visits all the cities. Similarly, one can also model scheduling problems in terms of the chromatic number of a graph (which is the smallest number of colours with which one can colour its vertices so that no adjacent vertices receive the same colour).From a theoretical point of view it is important to gain a better understanding of the relationship and the influence of the basic graph parameters like minimum degree, connectivity, girth and chromatic number. The increasing use of techniques like the probabilistic method and tools like the Regularity lemma and the Blow-up lemma has contributed to much recent progress in this field. However, I believe that their potential is far from fully explored. Roughly speaking, using the probabilistic method means that one demonstrates the existence of the desired object or configuration not constructively, but by showing that it appears with positive probability in a suitably designed probability space. While this might sound like a strange idea at first, it does provide a powerful approach, with applications ranging from theoretical computer science to number theory and analysis.The first area of the project concerns packing and embedding problems for graphs. One of the most famous results here is Dirac's theorem, which states that every graph G with n vertices and minimum degree at least n/2 contains a Hamilton cycle, i.e. a cycle which contains all of its vertices. Another important example is Hall's marriage theorem, which gives a necessary and sufficient condition for the existence of a perfect matching in a bipartite graph G, i.e. a set of disjoint edges containing all vertices of G. More generally, given two graphs F and G, we say that a perfect F-packing in G is a collection of disjoint copies of F in G that cover all the vertices of G. A celebrated result of Komlos, Sarkozy and Szemeredi gives a necessary condition for the existence of a perfect F-packing in G in terms of the chromatic number of F and the minimum degree of G. However, it has recently emerged that perhaps the so-called critical chromatic number of F is the correct parameter to look at and the main aim of the first part of the project is to settle this question.The second area is concerned with extremal problems for hypergraphs. Similar packing and embedding question to the ones discussed above arise also if we consider r-uniform hypergraphs instead of graphs (so instead of edges, we now have hyperedges, each consisting of r vertices). Unfortunately, the corresponding problems turn out to be much harder to solve in the hypergraph case, so little is known so far. However, the area has been going through spectacular growth recently due to the advent of new tools like the so-called hypergraph regularity lemma. One of the aims in this part of the project is to prove an analogue of the abovementioned theorem of Dirac for r-uniform hypergraphs.The third area is concerned with minors and subdvisions in graphs and directed graphs. Minors and subdivisions may be considered as a generalization of subgraphs. They arise quite naturally, for instance planar graphs (i.e. graphs that can be embedded in the plane without crossing edges) can be charactarized by forbidden subdivisions. However, the existence of subdivisions in graphs in which every edge is directed is far from understood. One aim in the last part of the project is obtain more insight here.