Combinatorics Seminar

When: Sunday, June 7, 10am Where: Schreiber 309 Speaker: Ehud Friedgut, Hebrew U. and the U. of Toronto Title: Intersecting families of permutations, an algebraic approach.

Abstract:

Much of extremal combinatorics deals with understanding families of sets given some information on their intersection pattern. The fundamental example of this is the Erdos-Ko-Rado theorem which characterizes maximal intersecting families. In this talk we study analogous questions where the sets are replaced by permutations, (with the appropriate definition of intersection), and prove some Erdos-Ko-Rado type results conjectured by Deza-Frankl and Cameron-Ku. The approach we use involves analyzing the spectral properties of weighted graphs that encode these structures, which leads us to problems related to the representations of the symmetric group. No prior knowledge of representation theory will be assumed.

Joint work with Haran Pilpel. Manuscript will be posted on the web shortly, jointly with David Ellis, who achieved the same results independently.