On some extremal results for order types

Abstract

A \textit{configuration} is a finite set of points in the plane. Two configurations $A$ and $B$ have the same \textit{order type} if there exists a bijection between them preserving the orientation of every ordered triple.  We investigate the following extremal problem on embedding configurations in general position in integer grid. Given an order type~$B$, let~$\ex(N,B)$ be the maximum integer~$m$ such that there exists a subconfiguration of the integer grid~$[N]^2$ of size~$m$ without a copy of~$B$.  An application of the celebrated multidimensional Szemer\'edi's theorem gives~$\ex(N,B)=o(N^2)$.
We first prove a subquadratic upper bound for all large order types $B$ and large $N$, namely, $\ex(N, B)\le N^{2-\eta}$ for some $\eta=\eta(B)>0$.  Then we give improved bounds for specific order types: we show that $\ex(N, B)= O(N)$ for the convex order type~$B$, and $\ex(N, B) = N^{3/2+o(1)}$ for those $B$ satisfying the so-called Erd\H{o}s--Hajnal property.  Our approach is to study the inverse problem, that is, the smallest $N_0=N_0(\alpha, B)$ such that every $\alpha$ proportion of $[N_0]^2$ contains a copy of $B$.