- Series
- Combinatorics Seminar
- Time
- Thursday, September 25, 2008 - 12:05pm for 1.5 hours (actually 80 minutes)
- Location
- Skiles 255
- Speaker
- Hanno Lefmann – Technical University Chemnitz, Germany
- Organizer
- Prasad Tetali
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.