Seminars & Colloquia Calendar
New Results on Projections
Guy Moshkovitz (IAS)
Location: Hill 705
Date & time: Monday, 03 February 2020 at 2:00PM - 3:00PM
Abstract: What is the largest number of projections onto k coordinates guaranteed in every family of m binary vectors of length n?
This fundamental question is intimately connected with important topics and results in combinatorics and computer science (Turan numbers, the Sauer-Perles-Shelah Lemma, the Kahn-Kalai-Linial Theorem), and is generally wide open.
We (essentially) settle the question for a wide range of parameters: linear k and sub-exponential m.
Based on joint work with Noga Alon and Noam Solomon.