RUS  ENG
Full version
JOURNALS // Modelirovanie i Analiz Informatsionnykh Sistem // Archive

Model. Anal. Inform. Sist., 2009 Volume 16, Number 2, Pages 22–74 (Mi mais52)

This article is cited in 5 papers

On Erdős–Szekeres problem for empty hexagons in the plane

V. A. Koshelev

Steklov Mathematical Institute, Russian Academy of Sciences

Abstract: In this work we consider a classical problem of Combinatorial Geometry of P. Erdős and G. Szekeres. The problem was posed in the 1930's. We investigate the minimum number $h(n)$ such, that for each $h(n)$-point set $A$ in general position in the plane there exists an $n$-point subset $B$ such, that the convex hull $C$ of $B$ is a convex empty $n$-gon, that is $(A\setminus B)\cap C=\emptyset$. Only recently T. Gerken has shown that $h(6)<\infty$. He has established the inequality $h(6)\le 1717$. The main result of the paper is the following inequality $h(6)\le 463$.

Keywords: general position, convex polygons, Ramsey theory.

UDC: 519+513

Received: 22.03.2009



© Steklov Math. Inst. of RAS, 2025