%A Han, Jie
%A Kohayakawa, Yoshiharu
%A Sales, Marcelo Tadeu
%A Stagni, Henrique
%D 2019
%T On some extremal results for order types
%K
%X 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$.
%U http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1305
%J Acta Mathematica Universitatis Comenianae
%0 Journal Article
%P 779-785%V 88
%N 3
%@ 0862-9544
%8 2019-08-01