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.

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