|
%I #23 Nov 28 2019 08:08:17
%S 4,4,4,6,6,7,8,8,8
%N Let Sq(n) denote the square grid consisting of all lattice points (x,y) such that x,y are in {0,1,...,n}. a(n) is the minimum number t such that there are t of the (n+1)^2 lattice points in Sq(n) so that the binomial(t,2) lines that they determine cover all points in Sq(n).
%C No exact values are given in the paper by Alon, however one will find there upper and lower bounds involving unknown constants for the d-dimensional generalization of this sequence.
%C The upper bound a(n) <= 2(n+1) is found by choosing n+1 lines parallel to one of the square's edges, fixed by 2(n+1) points on 2 opposite edges of the grid. Another upper bound a(n) <= 3 + A018805(floor((n+1)/2)) is obtained by placing one point at the grid center (n even) or at one of the 4 grid points closest to the center (n odd), then letting 2+A018805(...) lines intersect there. - _R. J. Mathar_, Jan 24 2008
%C From _Rob Pratt_, Jul 22 2015: (Start)
%C Because each line covers at most n-1 unchosen points, we have (n-1) * binomial(t,2) >= (n-1)^2 - t, yielding a lower bound of a(n) >= ceiling((n - 3 + sqrt(8n^3 + 9n^2 - 14n + 1))/(2*(n-1))).
%C Can be formulated as an integer linear programming problem as follows. Let binary variable x[i,j] = 1 if lattice point (i,j) is chosen, and 0 otherwise. Let binary variable y[k] = 1 if line k is chosen, and 0 otherwise. The objective is to minimize sum x[i,j]. Let L[k] denote the set of lattice points on line k. The covering constraint for lattice point (i,j) is sum {k: (i,j) in L[k]} y[k] >= 1. To enforce the rule that y[k] = 1 implies sum {(i,j) in L[k]} x[i,j] >= 2, impose the linear constraint sum {(i,j) in L[k]} x[i,j] >= 2 * y[k]. (End)
%H N. Alon, <a href="http://www.math.tau.ac.il/~nogaa/PDFS/lattice.pdf">Economical coverings of sets of lattice points</a>, Geometric and Functional Analysis 1(3) (1991), pp. 225-230. doi:10.1007/BF01896202
%H R. J. Mathar, <a href="http://www.arxiv.org/abs/0811.2434">Finite Square Lattice Vertex Cover by a Baseline Set Defined With a Minimum Sublattice</a>, arXiv:0811.2434 [math.CO], 2008.
%e a(1) = 4 since the square Sq(1) = {(0,0),(1,0),(0,1),(1,1)} cannot be covered by lines determined by 3 points, but is covered by the lines determined by all 4 points in Sq(1).
%K nonn,hard,more
%O 1,1
%A _W. Edwin Clark_, Mar 15 2006
%E a(7)-a(9) from _Rob Pratt_, Jul 22 2015
|
