Colloquium
3:00 p.m., Wednesday (February 2, 2005)
WEST MALL ANNEX 110 (PIMS Facility)
Josh Cooper
Courant Institute, New York University
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 randomlike 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).
