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

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

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.