|
Search: id:A116446
|
|
|
| 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
1
|
| |
|
|
OFFSET
|
1,1
|
|
|
COMMENT
|
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 (mathar(AT)strw.leidenuniv.nl), Jan 24 2008
|
|
REFERENCES
|
N. Alon, Economical Coverings of Sets of Lattice Points, Geometric and Functional Analysis, Vol. 1, No. 3 (1991), pp. 225-230. Also available at http://www.math.tau.ac.il/~nogaa/PDFS/lattice.pdf
|
|
LINKS
|
N. Alon, Economial coverings of sets of lattice points, Geometric and Functional Analysis, vol. 1 (1991), 225-230.
R. J. Mathar, Finite Square Lattice Vertex Cover by a Baseline Set..., arXiv:0811.2434 [math.CO].
R. J. Mathar, Illustration of coverings n=3-5.
|
|
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: A160401 A114742 A098013 this_sequence A073229 A102126 A097918
Adjacent sequences: A116443 A116444 A116445 this_sequence A116447 A116448 A116449
|
|
KEYWORD
|
hard,more,nonn
|
|
AUTHOR
|
W. Edwin Clark (eclark(AT)math.usf.edu), Mar 15 2006
|
|
|
Search completed in 0.002 seconds
|
