New Results on Projections

New Results on Projections - Guy Moshkovitz

Guy Moshkovitz
Member, School of Mathematics
January 22, 2019

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 to important topics and results in combinatorics and computer science (Turan number, Sauer-Shelah Lemma, Kahn-Kalai-Linial Theorem, and more), and is wide open for most settings of the parameters. We essentially settle the question for linear k and sub-exponential m. 

Based on joint work with Noga Alon and Noam Solomon.