Ramsey theory: an extremal perspective

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

The underlying motto of Ramsey theory is that "total disorder is impossible". This means that in a large mathematical structure we can find some unavoidable, non-random, substructure. For instance, the van der Waerden theorem dating from 1927 states that, in any partition of the whole numbers into two sets, one of the sets must contain a long arithmetic progression. Ramsey-type theorems also have roots in different branches of mathematics, and the theory developed from them has influenced diverse areas such as number theory, logic, probability theory, geometry and theoretical computer science.The study of Ramsey theoretic questions has been especially fruitful in the context of graphs and hypergraphs. Here graphs consist of vertices and every pair of them may be joined by an edge. They are often used for studying social, infrastructure, telecommunication and biological networks. A typical Ramsey-type problem in graphs is to seek a monochromatic copy of a predetermined graph G in any red/blue-edge-colouring of a complete graph on n vertices. From the classical Ramsey theorem from 1930, we know that this statement holds providing n (the number of vertices in the complete graph) is sufficiently large. Determining the smallest such n, which is called the Ramsey number, is one of the most notorious open problem in combinatorics. When G is a complete graph on t vertices (with every pair of vertices joined by an edge), the Ramsey number is exponential in t. On the other hand, a conjecture of Burr and Erdos from 1973 states that if G is sparse, then its Ramsey number is only linear in the number of vertices. Tackling this conjecture has resulted in the development of powerful techniques and this conjecture has only been confirmed by a recent breakthrough of Lee. However, much less is known for Ramsey theory for hypergraphs and in fact, only a handful of Ramsey numbers are known in this setting. Hypergraphs are natural generalisations of graphs, where edges consist of more than two vertices (rather than two as in the case of graphs). Hypergraphs are often used to model more complicated networks with non-binary relationships, for example, for chemical reactions and machine learning. However, hypergraphs behave very differently to graphs and many core techniques in graph theory have yet (or even fail) to extend to the hypergraph setting. For instance, depending on the sparseness being considered, the Ramsey number of a sparse hypergraph may be linear or exponential in term on the number of vertices. The proposed research has three main strands. Firstly, to classify the families of sparse hypergraphs that have linear Ramsey numbers. Secondly, to study the behaviour of Ramsey numbers for hypergraphs with small expansion property. Thirdly, to develop a unified approach to the construction of monochromatic cycle partitions of edge-coloured hypergraphs. We anticipate that our methods (including a novel 'blueprint' approach to finding the required structures) will have further applications to related areas such as extremal hypergraph theory.