Combinatorics Seminar
When: Sunday, March 2, 10am
Where: Schreiber 309
Speaker: Nathan Linial, Hebrew University,
Title: Word maps and their combinatorial significance
Abstract:
Let w be a formal word in the formal letters g_1,...,g_k and let n
be an integer. Associate with every g_j a random permutation \pi_j
from S_n (the groups of all permutations on [n]). As a result we
obtain from w some random permutation. The map from the word w to
the resulting permutation is called the word map of w. How many
fixed points, cycles of length 2 or more generally how many L-cycles
does the resulting permutation typically have? A beautiful theorem
of Nica (1994) gives the answer: There is a limit distribution for
these numbers (as n grows). What is rather surprising is
that this limit distribution barely depends on the word w. For
example, the answer is one and the same for every w that is primitive
(i.e. when w cannot be expressed as w=u^d for some word u and d > 1).
I will describe a new and conceptual proof for this theorem and then
explain some consequences of this method in the study of eigenvalues
of graphs. I will also mention some related open problems.
A joint work with Doron Puder.