Points in almost general position

10 February 2015
14:30
Luka Milicevic
Abstract

Erdős asked the following question: given a positive integer $n$, what is the largest integer $k$ such that any set of $n$ points in a plane, with no $4$ on a line, contains $k$ points no $3$ of which are collinear? Füredi proved that $k = o(n)$. Cardinal, Toth and Wood extended this result to $\mathbb{R}^3$, finding sets of $n$ points with no $5$ on a plane whose subsets with no $4$ points on a plane have size $o(n)$, and asked the question for the higher dimensions. For given $n$, let $k$ be largest integer such that any set of $n$ points in $\mathbb{R}^d$ with no more than $d + 1$ cohyperplanar points, has $k$ points with no $d + 1$ on a hyperplane. Is $k = o(n)$? We prove that $k = o(n)$ for any fixed $d \geq 3$.

  • Combinatorial Theory Seminar