Combinartorics and TCS seminar
Friday, 24 November 11.30 am
======================
Venue: Ramanujan Hall
Host: Niranjan Balachandran
Speaker: Shagnik Das
Affiliation: National University of Taiwan
Title: Covering grids with multiplicity
Abstract: It is a fairly simple exercise to determine the minimum number of
hyperplanes needed to cover all the points of a finite grid $S_1 \times S_2 \times \dots \times S_d \in \mathbb{F}^d$. However, the situation becomes much more complex if you add the condition that one of the points of the grid must be avoided, leading to a classic problem in combinatorial geometry. This was resolved by Alon and Füredi in a classic result that popularised the use of algebraic methods in combinatorics. The recent work of Clifton and Huang, in which they considered the question a variant of the problem where the nonzero points of a hypercube should be covered multiple times while avoiding the origin, brought renewed interest to this problem. In addition to Alon-Füredi-style algebraic arguments, they used linear programming to asymptotically resolve the problem in certain ranges. Despite all the attention this problem has received, there remain many open problems, even in the case of two-dimensional grids over $\mathbb{R}$. In this talk, after surveying the background and introducing the techniques used, we shall present some recent results that resolve the problem for almost all two-dimensional grids. The new results are joint work with Anurag Bishnoi, Simona Boyadzhiyska, and Yvonne den Bakker, and separately with Valjakas Djaljapayan, Yen-Chi Roger Lin, and Wei-Hsuan Yu.