Seminars & Colloquia Calendar
New Results on Projections
Guy Moshkovitz - Rutgers/DIMACS
Location: CoRE 301
Date & time: Wednesday, 04 September 2019 at 11:00AM - 12:00PM
Abstract: What is the largest number of projections onto k coordinates guaranteed in every set of m binary vectors of length n? This fundamental question is intimately connected to important topics and results in combinatorics and computer science (Turan numbers, the Sauer-Perles-Shelah Lemma, the Kahn-Kalai-Linial Theorem, and more), and is wide open for most settings of the parameters. We essentially settle the question for all linear k and sub-exponential m.
Based on joint work with Noga Alon and Noam Solomon