The sparse hypergraph regularity method

这个项目的主要目的是加深我们对超图的结构的理解。为了解释超图的概念，我们从图开始。图是一种抽象结构，它对两个身体的互动进行建模，例如社交网络中的友谊、物理网络中的链接或街道地图等。相互作用的对被认为形成了一条边。我们对图表的行为有很好的理解，事实上，这是当今经济的一大部分基础。仅举一个突出的例子，谷歌的成功主要归功于组合优化--图上的算法。特别是，让公司起步的PageRank算法来自于对图论的学术研究。正则性方法是图论分支中研究图的极值性质的最重要的工具箱之一。图不能模拟多体相互作用。这样做的抽象结构是超图，其中边可以包含两个以上的实体，而我们对超图没有很好的理解。理论计算机科学对此有很好的理论解释：简而言之，图上的许多基本计算问题都很容易解决，但有强有力的迹象表明，超图等价物并非如此。但这肯定不是故事的全部。可以克服这一缺陷的一个方面是极值组合学。超图的正则化方法已经有了，但发展并不完整，现有的理论很难应用。这个项目的一部分是完成开发，并以一种便于应用的方式简化该理论，使其与图形版本的状态相匹配。该项目的第二部分-与以上密切相关-是开发超图正则性理论的“稀疏版本”。这是为了解决原始正则性方法的一个普遍问题：它只适用于“密集”的图，即系统中相当大一部分对是边的图。这一假设不适用于许多现实世界的例子，也不适用于来自概率组合学或其他数学领域的(超)图。该项目这一部分的目标是能够处理稀疏但看起来很随机的系统。在我们的理解中，在这个阶段，不可能避免最后一个假设。举一个可以应用这种理论的例子，素数看起来是随机的，但当你看到越来越大的数字时，它们也会变得稀疏--它们是稀疏的。数学中一些最广为人知的问题来自素数：我们多久能找到相差两个的素数对？所有偶数都是两个素数的和吗？我们能找到1,000,000个素数，它们构成一个序列，在每对连续的素数之间有相等的间隔吗？格林和陶渊明出色地解决了最后一个问题：我们可以。最近，Conlon、Fox和赵解释说，解决方案实际上分为数论部分和纯组合学部分-事实上，一个相当基本的稀疏超图正则性理论可以解决这个问题。因此，开发完整版本的超图将在素数理论和离散数学中结出硕果。该项目的最后部分是研究超图中的路和圈的结构。这些在图表中也得到了很好的理解，这种理解是许多更复杂的证明的基础，包括那些使用正则性方法的证明。在超图中，我们又一次没有很好地理解它们，再次获得这样的理解将完美地补充关于超图正则性方法的工作。

The broad aim of this project is to further our structural understanding of hypergraphs. To explain the concept of a hypergraph, we begin with graphs. A graph is an abstract structure which models two-body interactions, such as friendship in a social network, links in a physical network or street map, and so on. Pairs that interact are said to form an edge. We have a good understanding of how graphs behave, and in fact this underpins a large fraction of today's economy. To give just one prominent example, Google's success is mainly down to combinatorial optimisation - algorithms on graphs. In particular the PageRank algorithm, which got the company started, came from academic research into graph theory. One of the most important toolboxes in the branch of graph theory that studies extremal properties of graphs is the regularity method.A graph cannot model multi-body interactions. The abstract structure which does this is a hypergraph, where edges can contain more than two entities, and we do not have a good understanding of hypergraphs. There are some good theoretical reasons for this coming from Theoretical Computer Science: briefly, many fundamental computational problems on graphs are known to be soluble easily, whereas there are strong indications the same is not true for the hypergraph equivalents. But this is certainly not the whole story. One aspect where the deficiency can be overcome comes from extremal combinatorics. There is a regularity method for hypergraphs, but the development is not complete and the existing theory is very hard to apply. Part of this project is to complete the development and to simplify the theory in a way that allows for easy application, matching the state of the graph version.A second part of this project - intimately linked with the above - is to develop a 'sparse version' of the hypergraph regularity theory. This is an attempt to address a general problem with the original regularity method: it only works for graphs which are 'dense', that is, where a significant fraction of pairs in the system are edges. This assumption is not the case for many real world examples, and it is also not the case for (hyper)graphs coming from probabilistic combinatorics, or from other areas of mathematics. The aim of this part of the project is to be able to deal with systems which are sparse, but 'look random'. At this stage in our understanding, it is not possible to avoid this last assumption. To give an example of where one can apply such a theory, the prime numbers 'look random', but they also thin out as one looks at larger and larger numbers - they are sparse. Some of the most well-known problems in mathematics come from the prime numbers: how often do we find pairs of primes that differ by two? are all even numbers the sum of two primes? can we find 1,000,000 primes which form a sequence with equal gaps between each consecutive pair? The last of these problems was spectacularly solved by Green and Tao: we can. Recently, Conlon, Fox and Zhao explained that the solution really splits up into a number-theoretic part and a part which is pure combinatorics - in fact, a problem which a rather basic sparse hypergraph regularity theory solves. Developing a full version of the same will thus bear fruit in the theory of prime numbers as well as discrete mathematics.The final part of the project is to study the structure of paths and cycles in hypergraphs. These are again very well understood in graphs, and this understanding is a backbone of many more sophisticated proofs, including those using the regularity method. In hypergraphs, again we do not understand them well, and again obtaining such an understanding will complement work on the hypergraph regularity method perfectly.