Intersection sizes of linear subspaces with the hypercube

Journal article (2020)

Authors

C.E. Groenland University of Oxford
Tom Johnston University of Oxford
Affiliation
External organisation
Intersection Hypercube Linear subspace
More Info
expand_more

Published Date

2020

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Affiliation

External organisation

Abstract

We continue the study by Melo and Winter (2019) [3] 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 2k−1 (the “large” sizes) are of the form 2k−1+2i. We show that this is almost true: the large intersection sizes are either of this form or of the form 35⋅2k−6. We also disprove a second conjecture of Melo and Winter by proving that a positive fraction of the “small” values is missing.