Avoiding Grid-Points in Affine or Linear Spaces of Small Dimension

Combinatorics Seminar
Thursday, September 25, 2008 - 12:05
1.5 hours (actually 80 minutes)
Skiles 255
Technical University Chemnitz, Germany
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.