Ramsey theory: an extremal perspective

拉姆齐理论的基本格言是“完全无序是不可能的”。这意味着在一个大的数学结构中，我们可以找到一些不可避免的、非随机的子结构。例如，可以追溯到1927年的范德沃登定理指出，在将所有数分成两个集合的任何一个集合中，其中一个集合必须包含一个长的算术级数。Ramsey-型定理也植根于不同的数学分支，由此发展出的理论影响了数论、逻辑、概率论、几何学和理论计算机科学等多个领域，尤其是在图和超图的背景下，Ramsey理论问题的研究成果尤其丰硕。这里，图由顶点组成，每一对顶点都可以由一条边连接起来。它们经常被用于研究社会、基础设施、电信和生物网络。图中一个典型的Ramsey型问题是在n个顶点的完全图的任何红/蓝边着色中寻找预定图G的单色副本。从1930年以来的经典Ramsey定理我们知道，如果n(完全图中的顶点数)足够大，这一命题是成立的。确定这样的最小n，即Ramsey数，是组合数学中最臭名昭著的公开问题之一。当G是t个顶点的完全图(每对顶点都有一条边连接)时，Ramsey数是t的指数。另一方面，1973年Burr和Erdos的一个猜想指出，如果G是稀疏的，那么它的Ramsey数在点数上只是线性的。解决这一猜想导致了强大技术的发展，而这一猜想只有在Lee最近的一项突破中才得到证实。然而，超图的Ramsey理论鲜为人知，事实上，在这种情况下只有少数几个Ramsey数是已知的。超图是图的自然推广，其中边由两个以上的顶点组成(而不是像图那样由两个顶点组成)。超图经常被用来对具有非二元关系的更复杂的网络进行建模，例如，用于化学反应和机器学习。然而，超图的行为与图非常不同，图论中的许多核心技术尚未(甚至失败)扩展到超图设置。例如，根据所考虑的稀疏性，稀疏超图的Ramsey数可以是关于顶点数量的线性或指数。这项拟议的研究有三个主要方面。首先，对具有线性Ramsey数的稀疏超图族进行分类。其次，研究了具有小扩张性质的超图的Ramsey数的性质。第三，建立了边色超图单色圈划分的统一构造方法。我们期望我们的方法(包括一种新的寻找所需结构的“蓝图”方法)将进一步应用于相关领域，如极值超图理论。

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.