

A116446


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).


0




OFFSET

1,1


COMMENTS

No exact values are given in the paper by Alon, however one will find there upper and lower bounds involving unknown constants for the ddimensional generalization of this sequence.
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
From Rob Pratt, Jul 22 2015: (Start)
Because each line covers at most n1 unchosen points, we have (n1) * binomial(t,2) >= (n1)^2  t, yielding a lower bound of a(n) >= ceiling((n  3 + sqrt(8n^3 + 9n^2  14n + 1))/(2*(n1))).
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)


LINKS

Table of n, a(n) for n=1..9.
N. Alon, Economical coverings of sets of lattice points, Geometric and Functional Analysis 1(3) (1991), pp. 225230. doi:10.1007/BF01896202
R. J. Mathar, Finite Square Lattice Vertex Cover by a Baseline Set Defined With a Minimum Sublattice, arXiv:0811.2434 [math.CO], 2008.


EXAMPLE

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).


CROSSREFS

Sequence in context: A273909 A098013 A073229 * A102126 A277433 A219760
Adjacent sequences: A116443 A116444 A116445 * A116447 A116448 A116449


KEYWORD

nonn,hard,more


AUTHOR

W. Edwin Clark, Mar 15 2006


EXTENSIONS

a(7)a(9) from Rob Pratt, Jul 22 2015


STATUS

approved



