Combinatorics: Yuval Filmus (Technion)

Mon, 18/10/202115:00-17:00
HUJI Combinatorics Seminar 

When: Monday, October 18th, 2021, 3PM (Israel time)
Where: B400

Speaker:  Yuval Filmus (Technion)

Title: When is a linear function on S_n almost Boolean?

A real-valued function on S_n is *linear* if it is a linear combination of indicators of the form "i goes to j".
Ellis, Friedgut and Pilpel showed that if a linear function on S_n is Boolean then it is a *dictator*, that is, it depends on the image of some i or on the inverse image of some j.
What can we say about linear functions on S_n which are *almost* Boolean?
We answer this question completely for several notions of "almost", improving on earlier results together with Ellis and Friedgut.