Randomness in High-Dimensional Combinatorics: Colorings, Robustness, and Statistics

图是离散的数学结构，对对象之间的成对关系进行建模，是组合学的基础。从几何/拓扑的观点来看，它们是一维对象。对许多图论概念的高维理论的追求是一个富有成果的研究领域。在过去的半个世纪里，概率方法的引入对这一领域产生了巨大的影响，对随机性的研究将是这一项目的核心。这个项目将专注于开发高维版本的图嵌入和分解。研究生和本科生将作为这个项目的一部分接受培训。本建议的主要焦点是图和超图的嵌入和分解，特别强调“高维组合学”中的问题。超图嵌入和分解是现代组合学的核心问题，但也包括一些最古老的组合问题。例如，9世纪著名的“骑士之旅”问题和19世纪的“伊科斯博弈”都是嵌入问题。两者都可以理解为在一个特定的图中找到哈密顿环的问题。18、19世纪关于拉丁方格和组合设计的一些最著名和最有影响力的组合问题，现在被理解为超图分解问题。这个项目的目标包括：(1)使用随机性来证明新的嵌入和分解结果；(2)使用最近引入的“蔓延”概念来证明这些结果的“鲁棒”版本；(3)调查随机组合设计的统计方面。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Graphs are discrete mathematical structures that model pairwise relations between objects, and they are fundamental to combinatorics. From a geometric / topological viewpoint, they are one-dimensional objects. The pursuit of a higher-dimensional theory of many graph theoretic concepts has been a fruitful area of research. In the last half century, the introduction of the probabilistic method has had a tremendous impact on this area, and the study of randomness will be central to this project. This project will focus on developing a high-dimensional version of graph embeddings and decompositions. Graduate and undergraduate students will be trained as part of this project.The primary focus of this proposal is embeddings in and decompositions of graphs and hypergraphs, with a particular emphasis on problems in “high-dimensional combinatorics”. Hypergraph embeddings and decompositions are a central concern in modern combinatorics but also include some of the oldest combinatorial problems. For example, the famous “Knights Tour” problem, studied in the 9th century, and the “Icosian Game” of the 1800s, are both embedding problems. Both can be understood as the problem of finding a Hamilton cycle in a particular graph. Some of the most famous and influential combinatorial questions from the eighteenth and nineteenth century on Latin squares and combinatorial designs are now understood as hypergraph decomposition problems. Goals of this project include (1) using randomness to prove new embedding and decomposition results (2) proving "robust" versions of these results using the recently introduced notion of "spreadness" and (3) investigating statistical aspects of random combinatorial designs.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.