Natural quasirandomness properties
Leonardo N. Coregliano, Alexander Alexandrovich Razborov · Random Structures and Algorithms · 2023
Abstract The theory of quasirandomness has greatly expanded from its inaugural graph theoretical setting to several different combinatorial objects such as hypergraphs, tournaments, permutations and so forth. However, these quasirandomness variants have been done in an ad‐hoc case‐by‐case manner. In this article, we propose three new hierarchies of quasirandomness properties that can be naturally defined for arbitrary combinatorial objects. Our properties are also “natural” in more formal sense: they are preserved by local combinatorial constructions. Similarly to hypergraph quasirandomness properties, we show that our quasirandomness properties have several different but equivalent characterizations. We also prove several implications and separations comparing them to each other and to what has been known for hypergraphs. The main notion explored is that of unique coupleability: two limit objects are uniquely coupleable if there is only one way to align (i.e., couple) them.