|
On higher multiplicity hyperplane and polynomial covers for symmetry-preserving subsets of the hypercube| title | On higher multiplicity hyperplane and polynomial covers for symmetry-preserving subsets of the hypercube |
|---|
| start_date | 2024/06/24 |
|---|
| schedule | 14h |
|---|
| online | no |
|---|
| location_info | salle 3052 |
|---|
| summary | Suppose we want to cover all the vertices of the n-dimensional Boolean cube using a minimum number of hyperplanes. Observe that this can be done using only two hyperplanes. Moreover, no single hyperplane can cover all the vertices. Now, what if we want to cover only a subset of the Boolean cube? For example, suppose we want to cover all the vertices except one, viz. the origin. One can observe that n hyperplanes are sufficient. But can we do better? The celebrated covering result by Alon and Füredi shows that at least n hyperplanes will be required to cover all the vertices of the n-dimensional cube leaving out exactly one vertex.
We shall discuss different versions of this covering problem, and give a generalization of Alon and Füredi’s covering result for any symmetric subset of the Boolean cube. Also, we shall show a strict separation between the size of a polynomial cover and a hyperplane cover.
This work was jointly done with Arijit Ghosh, Soumi Nandi, and S. Venkitesh. |
|---|
| responsibles | Hamoudi |
|---|
Workflow history| from state (1) | to state | comment | date |
|---|
| submitted | published | | 2024/06/20 12:11 UTC |
| |
|