Large Combinatorial Objects: Extremal Structure and Quasirandomness

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

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

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