Séminaire Lotharingien de Combinatoire, B15b (1986), 1
p.
[Formerly: Publ. I.R.M.A. Strasbourg, 1987, 340/S-15, p.
129.]
Walter Kern, Alfred Wanka
On a Problem about Covering Lines by Squares
Abstract.
Let S be the square [0,n]x[0,n] of side length n and let
T={S(1),...,S(t)} be a set of unit squares lying inside S, whose sides
are parallel to those of S. The set T is called a line cover, if
every line intersecting S also intersects some S in T.
Let t(n) denote the minimum cardinality of a line cover, and let
t'(n) be defined in the same way, except that we restrict our
attention to lines which are parallel to either one of the axes
or one of the diagonals of S. It has been conjectured by Toth
that t(n)=2n+0(1) and Baranyi and Füredi that
t(n)=(3/2)n+0(1). We will prove instead, t'(n)=(4/3)+0(1), and as
to Toth's conjecture, we will exhibit a ``non integer" solution to a
related LP-relaxation, which has size equal to (3/2)+0(1).
The following versions are available: