Subscribe to Events
Covering the hypercube with hyperplanes
Caleb Fong
Location: HLL-701
Date & time: Wednesday, 12 March 2025 at 12:15PM - 1:15PM
Abstract:
The n-dimensional Boolean hypercube Q_n can be easily covered with 2 hyperplanes. If you add the additional restriction that exactly one point must remain uncovered, it takes some work to show—as Alon and Furedi did in 1993—that you need at least n hyperplanes to cover the rest. We will see the quick Combinatorial Nullstellensatz proof of this result, along with some more recent work on k-fold hyperplane covers of the hypercube (minus a point) due to Alexander Clifton and Hao Huang in 2019.
The n-dimensional Boolean hypercube Q_n can be easily covered with 2 hyperplanes. If you add the additional restriction that exactly one point must remain uncovered, it takes some work to show—as Alon and Furedi did in 1993—that you need at least n hyperplanes to cover the rest. We will see the quick Combinatorial Nullstellensatz proof of this result, along with some more recent work on k-fold hyperplane covers of the hypercube (minus a point) due to Alexander Clifton and Hao Huang in 2019.