Large Combinatorial Objects: Extremal Structure and Quasirandomness

大型组合对象：极值结构和拟随机性

• 批准号: RGPIN-2021-02460
• 负责人: Noel, Jonathan
• 金额: $ 1.89万
• 依托单位: University of Victoria
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=759081
• 关键词: Large; Combinatorial; Objects; Extremal; Structure

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.

大型离散结构几乎遍及现代世界的每个方面。无序的粒子系统，社交网络和人脑都可以看作是由单个节点组成的庞大网络，它们之间的联系。分析巨大数据集的挑战会导致许多令人兴奋的数学问题。例如，在保留其关键信息的同时，我们如何以可理解的方式对大型数据集进行建模？在最近开发的组合对象的“极限”理论中可以找到许多结构的问题的答案。一个关键的想法是查看大型数据集，例如网络，不是作为离散结构，而是作为富裕对象的离散近似。为了进行类比，我们在日常生活中遇到的物理对象本质上是粒子网络，但是以这种方式考虑它们很少有用。我们选择基于连续特征（例如颜色和清晰度）的宝石，而不是在分子水平上排列的方式。同样，大型网络可以通过连续分析对象建模，以保留其许多最重要的功能。组合极限理论的核心是quasirandomness的概念。 quasirandomness的中心宗旨是，在随机组合物体中具有很高概率的许多看似不同的特性，彼此相等。如果对象具有这些属性，则称为“ quasirandom”。该提案中的一个问题是确定局部模式，这些模式表征了大型排列中的quasirandomness。这种类型的结果直接应用于独立性测试领域（即测试零假设）在30年代和40年代肯德尔和Hoeffding启动的非参数统计中。该观点表明几个有趣的高维扩展，例如，哪种局部统计数据表征了随机变量三重的相互独立性？另一个重点是局部模式频率对图中全局quasirandomness的影响。该区域的经典结果是Goodman Bound，它断言，在完整图的边缘的颜色中，单色三角形的数量通过随机颜色近似最小化。这种类型的陈述是由拉姆齐理论中的应用激发的，在这种情况下，利用有效的quasirandomness估计值（包括古德曼界限本身）。该区域与著名的Sidorenko猜想有关，这是双方子图的频率的。我的方法涉及将组合论证与来自分析，概率和优化等其他领域的方法融合。该多功能工具包将应用于图形，排列，锦标赛，有向图和超图的多种极端问题。这项工作的这一目的是开发功能强大且广泛适用的工具，用于从大型数据集中提取结构。