Geodesic
On the Erdős-Szekeres Problem for Convex Permutations and Orthogonally Convex Point Sets
The electronic journal of combinatorics, Tome 32 (2025) no. 4
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

A finite set of points is generic if no two points are on the same vertical or horizontal line. The set is orthogonally convex if every point has an empty quadrant. We study the smallest integer $N_o(n)$ such that every generic set of $N_o(n)$ points contains a orthogonally convex subset of size $n$. For even $n$, we prove $N_0(n) = \frac{1}{8}(n^2+2n+8)$, which is tight, and in the odd case we get close upper and lower bounds. To prove these results, we apply the theory of Greene and Kleitman (1976) and Frank (1980) about posets to the partial order of point sets in the plane. Generic sets correspond to permutations in a canonical way. A permutation is convex if it is order isomorphic to a finite generic set of points in convex position. The value of $N_o(n)$ is also the smallest $N$ such that every permutation of $N$ contains a convex subpermutation of size $n$.
DOI : 10.37236/13543

Heather S. Blake  1   ; Stefan Felsner    ; Rimma Hämäläinen    ; Marcin Witkowski 

1 Davidson College 
@article{10_37236_13543,
     author = {Heather S. Blake and Stefan Felsner and Rimma H\"am\"al\"ainen and Marcin Witkowski},
     title = {On the {Erd\H{o}s-Szekeres} {Problem} for {Convex} {Permutations} and {Orthogonally} {Convex} {Point} {Sets}},
     journal = {The electronic journal of combinatorics},
     year = {2025},
     volume = {32},
     number = {4},
     doi = {10.37236/13543},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/13543/}
}
TY  - JOUR
AU  - Heather S. Blake
AU  - Stefan Felsner
AU  - Rimma Hämäläinen
AU  - Marcin Witkowski
TI  - On the Erdős-Szekeres Problem for Convex Permutations and Orthogonally Convex Point Sets
JO  - The electronic journal of combinatorics
PY  - 2025
VL  - 32
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.37236/13543/
DO  - 10.37236/13543
ID  - 10_37236_13543
ER  - 
%0 Journal Article
%A Heather S. Blake
%A Stefan Felsner
%A Rimma Hämäläinen
%A Marcin Witkowski
%T On the Erdős-Szekeres Problem for Convex Permutations and Orthogonally Convex Point Sets
%J The electronic journal of combinatorics
%D 2025
%V 32
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/13543/
%R 10.37236/13543
%F 10_37236_13543
Heather S. Blake; Stefan Felsner; Rimma Hämäläinen; Marcin Witkowski. On the Erdős-Szekeres Problem for Convex Permutations and Orthogonally Convex Point Sets. The electronic journal of combinatorics, Tome 32 (2025) no. 4. doi: 10.37236/13543

Cité par Sources :