Extremal subsets of the boolean cube with respect to projections

Seminar
Speaker
Noam Solomon (Harvard University)
Date
10/06/2018 - 15:30 - 14:00Add to Calendar 2018-06-10 14:00:00 2018-06-10 15:30:00 Extremal subsets of the boolean cube with respect to projections In this talk, we will present an asymptotically tight bound on the largest number of distinct projections onto \alpha n coordinates guaranteed in any family of n^r binary vectors of length n, where 0 < \alpha \le 1 and r = n^{o(1)}, thus closing a gap open since a work of Bollobas and Radcliffe from 1995. For the proof, we establish a “sparse” version of a classical result, the Kruskal-Katona Theorem, where we give a stronger guarantee when the hypergraph does not induce dense subhypergraphs. We also present a geometric application regarding point-halfspace separation in R^d. The talk is based on a recent joint work with Noga Alon and Guy Moshkovitz. Room 201 , Math and CS Building אוניברסיטת בר-אילן - Department of Mathematics mathoffice@math.biu.ac.il Asia/Jerusalem public
Place
Room 201 , Math and CS Building
Abstract

In this talk, we will present an asymptotically tight bound on the largest number of distinct projections onto \alpha n coordinates guaranteed in any family of n^r binary vectors of length n, where 0 < \alpha \le 1 and r = n^{o(1)}, thus closing a gap open since a work of Bollobas and Radcliffe from 1995. For the proof, we establish a “sparse” version of a classical result, the Kruskal-Katona Theorem, where we give a stronger guarantee when the hypergraph does not induce dense subhypergraphs. We also present a geometric application regarding point-halfspace separation in R^d.

The talk is based on a recent joint work with Noga Alon and Guy Moshkovitz.

Last Updated Date : 26/11/2019