Rutgers Discrete Mathematics Seminar

Title: A Nice Basis for the Slice

Speaker: Yuval Filmus, IAS

Date: Monday, February 2, 2015 11:00 am

Location: CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ


The slice is the set of vectors in {0,1}^n of Hamming weight k. Consider the following three questions:

(1) I have a function on the slice. What is the correct way to extend it to {0,1}^n and beyond?
(2) Is there a Fourier basis for the slice?
(3) Is there an explicit orthogonal basis of eigenvectors for the Kneser and Johnson graphs?

Surprisingly, all these questions are connected. We answer them by giving a nice basis for functions on the slice, derived from Young's orthogonal basis for the symmetric group.