权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Ramsey theory: an extremal perspective

拉姆齐理论：极端观点

基本信息

批准号：
EP/V048287/1
负责人：
Siu Lun Lo
金额：
$ 39.95万
依托单位：
University of Birmingham
依托单位国家：
英国
项目类别：
Research Grant
财政年份：
2022
资助国家：
英国
起止时间：
2022 至无数据
项目状态：
未结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FV048287%2F1
关键词：
Ramsey theory 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.

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