Large Combinatorial Objects: Extremal Structure and Quasirandomness

大型离散结构几乎遍及现代世界的各个方面。无序粒子系统、社会网络和人类大脑都可以被视为由单个节点组成的庞大网络，这些节点之间有链接。分析大量数据集的挑战产生了大量令人兴奋的数学问题。例如，我们如何以一种可理解的方式对大型数据集进行建模，同时保留其关键信息？对于许多结构，这个问题的答案可以在最近发展的组合对象的“极限”理论中找到。一个关键的思想是把一个大的数据集，例如一个网络，不是作为一个离散的结构，而是作为一个更丰富的连续对象的离散近似。打个比方，我们在日常生活中遇到的物理物体本质上是粒子网络，但以这种方式思考它们很少有用。我们根据颜色和净度等连续特征来选择宝石，而不是根据它在分子水平上的排列方式。类似地，一个大型网络可以通过一个连续的分析对象以保留其许多最重要特征的方式建模。组合极限理论的核心是准随机性的概念。准随机性的一个核心原则是，在一个随机组合对象中，许多看似不同的、具有高概率的属性实际上是相互等价的。如果一个物体具有这些属性中的任何一个，就被称为“准随机”。该方案中的一个问题是在大排列中识别具有准随机性特征的局部模式。这种类型的结果直接应用于Kendall和Hoeffding在30年代和40年代发起的非参数统计中的独立性检验（即检验零假设）领域。这种观点提出了几个有趣的高维扩展，例如，什么样的局部统计特征的相互独立性的三组随机变量？另一个重点是局部模式频率对图中全局拟随机性的影响。该领域的经典结果是Goodman界，该界断言，在具有两种颜色的完全图的边缘的一种着色中，单色三角形的数量通过随机着色近似最小化。这种类型的陈述是由拉姆齐理论的应用驱动的，其中实质性的突破来自利用有效的准随机估计（包括Goodman边界本身）。这个区域与著名的关于二部子图频率的Sidorenko猜想有关。我的方法包括将组合论证与分析、概率和优化等其他领域的方法相结合。这个万能的工具包将应用于图、置换、竞赛、有向图和超图中的大量极值问题。这项工作的目的是开发强大而广泛适用的工具，用于从大型数据集中提取结构。

Large discrete structures pervade nearly every facet of the modern world. Disordered particle systems, social networks and the human brain can all be viewed as massive networks composed of individual nodes with links between them. The challenge of analyzing enormous data sets gives rise to a wealth of exciting mathematical problems. For example, how do we model a large data set in an intelligible way while preserving its crucial information? Answers to this question for many structures can be found in the recently developed "limit" theory for combinatorial objects. A key idea is to view a large data set, e.g. a network, not as a discrete structure, but as a discrete approximation of a richer continuous object. For an analogy, physical objects that we encounter in our everyday lives are essentially networks of particles, but it is rarely useful to think of them in that way. We select a gem based on continuous characteristics like colour and clarity, not on the way it is arranged at a molecular level. Similarly, a large network can be modeled by a continuous analytic object in a way that preserves many of its most vital features. At the heart of combinatorial limit theory is the concept of quasirandomness. A central tenet of quasirandomness is that many seemingly different properties which hold with high probability in a random combinatorial object turn out to be equivalent to one another. An object is said to be "quasirandom" if it has any of these properties. One problem in the proposal is to identify local patterns which characterize quasirandomness in a large permutation. Results of this type have direct applications to the area of independence testing (i.e. testing the null hypothesis) in nonparametric statistics initiated by Kendall and Hoeffding in the 30s and 40s. This viewpoint suggests several intriguing high-dimensional extensions, e.g., what sorts of local statistics characterize mutual independence of a triple of random variables? Another focus is on the influence of local pattern frequencies on global quasirandomness in graphs. A classical result in the area is the Goodman Bound which asserts that the number of monochromatic triangles in a colouring of the edges of a complete graph with two colours is approximately minimized by a random colouring. Statements of this type are motivated by applications in Ramsey Theory, where substantial breakthroughs have come from exploiting effective quasirandomness estimates (including the Goodman Bound itself). This area is linked to the famous Sidorenko Conjecture on frequencies of bipartite subgraphs. My approach involves blending combinatorial arguments with methods from other areas such as analysis, probability and optimization. This versatile toolkit will be applied to a multitude of extremal problems in graphs, permutations, tournaments, directed graphs and hypergraphs. This aim of this work is to develop powerful and widely applicable tools for extracting structure from large data sets.