Intersection sizes of linear subspaces with the hypercube

2018/10/05 by Groenland, Carla, Johnston, Tom
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1810.02729

Abstract

We continue the study by Melo and Winter [arXiv:1712.01763, 2017] on the possible intersection sizes of a k-dimensional subspace with the vertices of the n-dimensional hypercube in Euclidean space. Melo and Winter conjectured that all intersection sizes larger than 2^k-1 (the "large" sizes) are of the form 2^k-1+2ⁱ. We show that this is almost true: the large intersection sizes are either of this form or of the form 35⋅ 2^k-6. We also disprove a second conjecture of Melo and Winter by proving that a positive fraction of the "small" values is missing.

Related

• Cells in the box and a hyperplane
• On a covering problem in the hypercube
• Around the Complete Intersection Theorem
• The intersection spectrum of 3-chromatic intersecting hypergraphs
• Properties of sets of Subspaces with Constant Intersection Dimension