A superlinear lower bound on the number of 5-holes

DOI10.4230/LIPICS.SOCG.2017.8zbMATH Open1432.52027arXiv1703.05253OpenAlexW2964317353MaRDI QIDQ4580080FDOQ4580080

Authors: Oswin Aichholzer, Martin Balko, Jan Kynčl, Irene Parada, Manfred Scheucher, Pavel Valtr, Birgit Vogtenhuber, T. Hackl 

Publication date: 13 August 2018

Abstract: Let $P$ be a finite set of points in the plane in general position, that is, no three points of $P$ are on a common line. We say that a set $H$ of five points from $P$ is a $5$-hole in $P$ if $H$ is the vertex set of a convex $5$-gon containing no other points of $P$. For a positive integer $n$, let $h_5(n)$ be the minimum number of 5-holes among all sets of $n$ points in the plane in general position. Despite many efforts in the last 30 years, the best known asymptotic lower and upper bounds for $h_5(n)$ have been of order $Omega(n)$ and $O(n^2)$, respectively. We show that $h_5(n)=Omega(nlo{g}^{4/5}n)$, obtaining the first superlinear lower bound on $h_5(n)$. The following structural result, which might be of independent interest, is a crucial step in the proof of this lower bound. If a finite set $P$ of points in the plane in general position is partitioned by a line $ell$ into two subsets, each of size at least 5 and not in convex position, then $ell$ intersects the convex hull of some 5-hole in $P$. The proof of this result is computer-assisted.

Full work available at URL: https://arxiv.org/abs/1703.05253

Recommendations

• A superlinear lower bound on the number of 5-holes
• Lower bounds for the number of small convex \(k\)-holes
• On 5-gons and 5-holes
• On the minimum size of a point set containing a 5-hole and double disjoint 3-holes
• EMPTY CONVEX 5-GONS IN PLANAR POINT SETS

zbMATH Keywords

empty pentagon\(k\)-holeplanar point setempty \(k\)-gonErdős-Szekeres-type problem

Mathematics Subject Classification ID

Erd?s problems and related topics of discrete geometry (52C10) Lattices and convex bodies in (2) dimensions (aspects of discrete geometry) (52C05) Combinatorial complexity of geometric structures (52C45) Computer assisted proofs of proofs-by-exhaustion type (68V05)

Cited In (5)

• Empty rainbow triangles in \(k\)-colored point sets
• Two disjoint 5-holes in point sets
• On disjoint holes in point sets
• On 5-gons and 5-holes
• A superlinear lower bound on the number of 5-holes

This page was built for publication: A superlinear lower bound on the number of 5-holes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4580080)