top of page

The 2023 Project on Covering Grids with Hyperplanes 

This is a brief introduction to the 2023 Polymath Jr project that will be run by Anurag Bishnoi.

Given an n×m grid of points in the plane, what is the minimum number of lines needed to cover all points? The answer is simply the min{m,n}, and we can use horizontal/vertical lines to achieve this. The question becomes much more challenging when we want to cover all points except one, and no line in our collection is allowed to touch the forbidden point. In this case, the so-called polynomial method can be used to prove the (tight) lower bound of (m-1) + (n-1), and there is no known combinatorial/geometric proof of this result. The polynomial method approach can be extended to covering n₁ × n₂ × ··· × nₖ grids in ℝᵈ with hyperplanes.

 

In this project, we will explore variations of this problem that lead to some challenging open problems. Here are some examples.

 

1. Covering with multiplicities.

 

What is the minimum number of lines needed to cover every point of an   n × m grid at least k times, while missing one point?

 

In recent work, we have been able to answer this question for all "wide" grids (n much larger than m) and all "generic" grids, discovering some surprising new bounds using a linear programming approach, but many open problems remain. In particular, for the standard n × n grid, {0, 1, ..., n-1} × {0, 1, ..., n-1}, with (0, 0) as the forbidden point, we are only able to show that the minimum number of lines required is at least (2 - 1/√e - o(1)) k (n - 1) and at most (√2 + o(1)) k (n - 1), for n, k → ∞. Determining the precise answer would be very interesting.

 

We can also explore the higher dimensional case of this problem, and forbidding non-corner points. For more information, see this recent paper 

 

2. Changing the underlying field.

 

The questions described so far were inside the real space ℝᵈ. The problem of covering with multiplicities has a completely different behavior when we change ℝ with the finite field 𝔽q. In particular, even the case of binary fields 𝔽₂, is open (see https://arxiv.org/abs/2101.11947 for the current best results).

 

3. Forbidding larger sets of points.

 

Instead of forbidding one point of the grid, we could forbid multiple points, which also makes the problem much more difficult. Here are some interesting initial results in this direction:

 

We will pick the specific problems to work on depending on your interests, and there will be room for both theoretical and computational work in this project. Once you join the project you will get suggestions for the best problems to start with and possible approaches.

bottom of page