Personal tools
You are here: Home CG seminar 2018 Extremal subsets of the boolean cube with respect to projections
« December 2018 »
December
SuMoTuWeThFrSa
1
2345678
9101112131415
16171819202122
23242526272829
3031
Log in


Forgot your password?
 

Extremal subsets of the boolean cube with respect to projections

Wednesday, June 6th, 2018, 16:10

Schreiber 309

underline

Extremal subsets of the boolean cube with respect to projections

Noam Solomon, Harvard

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. 
Document Actions