Georgia Institute of Technology College of Sciences

Motivated by a question raised by P\'or and Wood in connection with compact embeddings of graphs into the grid {\mathbb Z}^d, we consider generalizations of the no-three-in-line-problem. For several pairs (d,k,l) we give algorithmic or probabilistic, combinatorial lower, and upper bounds on the largest sizes of subsets S of grid-points in the d-dimensional T \times ... \times T-grid, where T is large and no l distinct grid-points of S are contained in a k-dimensional affine or linear subspace.