On some extremal results for order types
Acta mathematica Universitatis Comenianae, Tome 88 (2019) no. 3, pp. 779-785
Jie Han; Yoshiharu Kohayakawa; Marcelo Tadeu Sales; Henrique Stagni; Jie Han; Yoshiharu Kohayakawa; Marcelo Tadeu Sales; Henrique Stagni. On some extremal results for order types. Acta mathematica Universitatis Comenianae, Tome 88 (2019) no. 3, pp. 779-785. http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a65/
@article{AMUC_2019_88_3_a65,
     author = {Jie Han and Yoshiharu Kohayakawa and Marcelo Tadeu Sales and Henrique Stagni and Jie Han and Yoshiharu Kohayakawa and Marcelo Tadeu Sales and Henrique Stagni},
     title = { On some extremal results for order types},
     journal = {Acta mathematica Universitatis Comenianae},
     pages = {779--785},
     year = {2019},
     volume = {88},
     number = {3},
     url = {http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a65/}
}
TY  - JOUR
AU  - Jie Han
AU  - Yoshiharu Kohayakawa
AU  - Marcelo Tadeu Sales
AU  - Henrique Stagni
AU  - Jie Han
AU  - Yoshiharu Kohayakawa
AU  - Marcelo Tadeu Sales
AU  - Henrique Stagni
TI  - On some extremal results for order types
JO  - Acta mathematica Universitatis Comenianae
PY  - 2019
SP  - 779
EP  - 785
VL  - 88
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a65/
ID  - AMUC_2019_88_3_a65
ER  - 
%0 Journal Article
%A Jie Han
%A Yoshiharu Kohayakawa
%A Marcelo Tadeu Sales
%A Henrique Stagni
%A Jie Han
%A Yoshiharu Kohayakawa
%A Marcelo Tadeu Sales
%A Henrique Stagni
%T On some extremal results for order types
%J Acta mathematica Universitatis Comenianae
%D 2019
%P 779-785
%V 88
%N 3
%U http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a65/
%F AMUC_2019_88_3_a65

Voir la notice de l'article provenant de la source Comenius University

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$.