Quasirandom combinatorial structures
- Daniel Kráľ (Masaryk University, Czech Republic)
Abstract
The study of properties that makes a combinatorial object (such as a permutation) to be quasirandom, i.e., to resemble a truly random object of the same kind, is an important and active line of research in combinatorics, which has various applications in computer science and statistics. The standard combinatorial way of comprehending quasirandomness evolved from nowadays classical results by Rödl, Thomason, and Chung, Graham and Wilson from the 1980s and appears in fundamental concepts in modern combinatorics such as the Regularity Method of Szemerédi.
The talk will start with discussing how the above mentioned classical results on quasirandom objects can be viewed through the lenses of the theory of combinatorial limits. We then employ analytic tools provided by the theory of combinatorial limits to solve several open problems concerning quasirandom objects of various kinds (in particular, directed graphs, permutations and Latin squares). At the end of the talk, we briefly explore the relation of presented results to the hypergraph regularity, which was developed independently by Gowers, and by Nagle, Rödl, Schacht and Skokan about two decades ago, and to the stochastic block model in statistics and network science.