On the number of points in general position in the plane

On the number of points in general position in the plane, Discrete Analysis 2018:16, 20 pp.

A recurring theme in combinatorics is questions of the following kind. Suppose that we have a combinatorial structure $S$ of size $n$ that contains no object of type $A$. Then how large a subset of $S$ can we find that contains no object of type $B$? For example, a graph with $n$ vertices that contains no clique of size 4 can be shown quite easily to have a triangle-free subgraph with $n^{1/2}$ vertices, and Wolfovitz has shown that there are graphs with no clique of size 4 and no triangle-free subgraph with more than $n^{1/2}(\log n)^{120}$ vertices.

One of the main questions discussed in this paper is perhaps the first question of this type one would think of in discrete geometry: if $S$ is a set of $n$ points in the plane and if no four of these points are collinear, then how large a subset of $S$ can one find with no three collinear?

A bound of $o(n)$ follows from the density Hales-Jewett theorem, which implies that a subset of $\{1,2,3\}^k$ of positive density contains three points in a line. It is not hard to project the set $\{1,2,3\}$ into the plane in such a way that collinearity is preserved, but no four points of the image lie in a line. However, the bound obtained this way is very weak – roughly $n/\log_*(n)$. This paper obtains the first reasonable bound for the problem, namely $n^{5/6+o(1)}$. It is not clear whether 5/6 is the right exponent, but the authors suggest that their construction may be close to optimal and that the difficulty is to calculate the correct exponent for that example.

Perhaps the most interesting aspect of the paper is that it uses the so-called method of containers. This method, developed by Saxton and Thomason, and independently by Balogh, Morris and Samotij, has already been used to solve a large number of important problems, but this appears to be the first time it has been used to solve a problem in discrete geometry, and it is used in a novel way.

They also use containers to prove a second discrete geometry result, this time about epsilon-nets. Given a family $\mathcal F$ of subsets of a finite set $X$, an $\epsilon$-net $E$ of $\mathcal F$ is a subset $E$ of $X$ such that every $F\in\mathcal F$ of size at least $\epsilon|X|$ contains an element of $E$. There are many interesting questions about the sizes of $\epsilon$-nets when $X$ is a geometrical set such as a finite set of points in the plane, and $\mathcal F$ is some natural class of subsets such as the set of all intersections of $X$ with convex bodies. With this example, one can also define a weak $\epsilon$-net as follows: it is a set of points $E$ in the plane, not necessarily a subset of $X$, such that every convex hull of at least $\epsilon|X|$ points of $X$ contains a point of $E$. Natural notions of weak $\epsilon$-nets can be defined in many other contexts too.

An interesting open question, asked by Noga Alon, is whether there is some natural geometrically defined family $\mathbb F$ of bounded VC-dimension such that the smallest $\epsilon$-net has size at least $(c/\epsilon)\log(1/\epsilon)$. Also using the density Hales-Jewett theorem, Alon obtained a bound that was very slightly superlinear in the case where $X$ was a certain point set and $\mathcal F$ was the set of all intersections of lines with $X$. In this paper, Alon’s bound is improved to $(1/\epsilon)\log(1/\epsilon)^{1/3-o(1)}$, which is much closer to the bound he suggests might be obtainable. They also obtain an improved bound for weak $\epsilon$-nets, but with a power of $\log\log(1/\epsilon)$ replacing the power of $\log(1/\epsilon)$. This construction has the additional feature that it works just as well in the projective plane.