login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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
4, 4, 4, 6, 6, 7, 8, 8, 8 (list; graph; refs; listen; history; text; internal format)
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 d-dimensional 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 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))).

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. 225-230. 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 2 09:22 EDT 2021. Contains 346422 sequences. (Running on oeis4.)