Shagnik Das, National University of Taiwan


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.

Ramanujan Hall, Department of Mathematics
Fri, November 24, 2023
Start Time
11:30am IST
Created by
Wed, November 22, 2023 11:28am IST