Seminar Details
New Results on Projections
- Start Date: February 3, 2020
- Event Start Time: 2:00 PM
- Event End Time: 3:00 PM
- Seminar Series: Rutgers Discrete Mathematics Seminar
- Presenter(s): Guy Moshkovitz - Institute for Advanced Study
- Event Location: Hill Center-Room 705
- Presentation Type: Stand Alone Presentation
- 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.