Suppose we want to cover all the vertices of the n dimensional hypercube {0,1}$^n$ using minimum number of hyperplanes. Observe that this can be easily done using only two hyperplanes: any two hyperplanes containing two opposite (n-1) dimensional faces are sufficient. Moreover, no single hyperplane can cover all the vertices. Now what if we want to cover only a subset of the hypercube? For example, suppose we want to cover all the vertices of {0,1}$^n$ except one vertex, viz. the origin, leaving out the origin as uncovered. One can observe that n hyperplanes are sufficient. But can we do better? The celebrated covering result by Alon and F$\ddot{u}$redi shows that at least n hyperplanes are necessary also. We shall discuss different versions of this covering problem and we shall prove a generalization of Alon and F$\ddot{u}$redi's covering result for any symmetric subset of the hypercube.
This work was jointly done with Arijit Ghosh, Chandrima Kayal and S. Venkitesh.
Short Bio: Soumi Nandi is a WALMART PREDOCTORAL FELLOW at the Computer Science and Automation (CSA) in the Indian Institute of Science (IISc), Bengaluru. She submitted her PhD thesis on July 31, 2024, as a student at the Advanced Computing and Microelectronics Unit (ACMU) in the Indian Statistical Institute (ISI), Kolkata, under the joint supervision of Sourav Chakraborty and Arijit Ghosh. Her research interests broadly include Combinatorics, Discrete Geometry, and Polynomial Methods. She is currently working on two types of problems: Geometric Transversal Theory and covering subsets of hypercubes with nice geometric objects.
