Quasirandom Permutations

Randomness plays an integral role in modern combinatorics, particularly when constructions are desired. However, it is unsatisfying to call a random object constructed, as no explicit description is given. This problem is notorious throughout Ramsey theory, number theory, and elsewhere. Since probabilistic methods have been so successful, it is desirable to provide constructions that resemble random ones in salient ways and, furthermore, to be able to measure the randomness of an object or class of objects. In fact, such measures have wide applications in structural combinatorial theory and beyond.

Quasirandomness is one such perspective on quantifying randomness. The set of properties true with high probability in a combinatorial space are partially ordered by implication; cliques of mutually equivalent properties are identified and given the induced ordering. Surprisingly large sets of natural random-like properties have been shown to belong to a single one of these property cliques in the case of graphs, hypergraphs, tournaments, and subsets of the finite cyclic groups. In this talk, we discuss the theory of quasirandom permutations, a subject that relates discrepancy theory, permutation statistics, and finite harmonic analysis. Almost all natural arithmetic permutations turn out to be highly quasirandom, and determining the relevant bounds provides a wealth of interesting questions in the theory of exponential sums. We discuss these and other examples, including the class of optimally quasirandom permutations, and we present several fundamental questions in this area.

Refreshments will be served at 2:45 p.m. in WMAX, Room 101 (the PIMS library).