Covering all except one of the purple intersection points of $n$ red and $m$ blue lines efficiently

Question

Consider a set of $n$ red lines and $m$ blue lines, suppose there are $nm$ distinct red-blue intersections.

What is the minimum number of lines $L_1,L_2,\dots, L_n$ such that the union contains all $nm$ intersection points except for exactly one?

A trivial construction is to take $n-1$ red lines and $m-1$ blue lines. I have not been able to find any case in which there is something better.

This problem is migrated from math.se , no advances were made.

Could someone point me to a more general family of problems or theory of this type?

Best Regards.

Answer 1

The very nice paper "Cayley-Bacharach theorems and conjectures" by David Eisenbud, Mark Green, and Joe Harris (http://www.ams.org/journals/bull/1996-33-03/S0273-0979-96-00666-0/home.html) gives an introduction to some related theory, including in particular a theorem which they number Theorem CB4: If $X_1$ and $X_2$ are two plane curves of degrees $d$ and $e$ meeting at $de$ distinct points, and if $C$ is any curve of degree $d+e-3$ containing all but one of the intersection points of $X_1$ and $X_2$, then $C$ contains all of the intersection points.

In particular, if any collection of $m+n-3$ lines covers $mn-1$ of the intersection points of the red and blue lines, then they have to cover all $mn$ intersection points (it's impossible to cover $mn-1$ and miss $1$, with $m+n-3$ or fewer lines). This shows that $m+n-2$ is the least number of lines that can cover $mn-1$ of the points and miss $1$.

Credit: I couldn't for the life of me dredge up the memory of "Cayley-Bacharach" until I read Douglas Zare's answer.

Answer 2

Problem 6 from the 2007 IMO is related. That problem was to determine the least number of hyperplanes needed to cover $\{0,1,...,n\}^3 \setminus \{(0,0,0)\}$, and the answer is $3n$. In general, the least number of hyperplanes needed to cover the lattice points in $\prod_{i=1}^k \{0,1,...,a_i\} \setminus \{\vec{0} \}$ is $\prod_{i=1}^k a_i$. This is an easy consequence of a deep result, the Combinatorial Nullstellensatz, which says that if $x_1^{e_1}...x_k^{e_k}$ is a term of highest degree of a polynomial $P$, and $S = \prod_{i=1}^k S_i,|S_i|=e_i$, then $P$ is nonzero at some point of $S$. This covers the case that the lines in each family are parallel (not just an evenly spaced grid).

For non-parallel lines, I don't know the answer in general. The $3\times 3$ case is covered by the Cayley-Bacharach Theorem, that if two cubic curves intersect in $9$ points, then if another conic passes through $8$ of those it must pass through the $9$th. The union of three lines is a cubic curve. So, the red lines and blue lines are two cubics intersecting in $9$ points, and if we have $3$ lines through $8$ of those points then they define another cubic which must include the last point.