A superlinear lower bound on the number of 5-holes

Oswin Aichholzer, Martin Balko, Thomas Hackl, Jan Kyncl, Irene Parada, Manfred Scheucher (Corresponding author), Pavel Valtr, Birgit Vogtenhuber

Research output: Contribution to journalArticleAcademicpeer-review

7 Citations (Scopus)

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 Ω(n) and O(n 2), respectively. We show that h 5(n)=Ω(nlog 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 ℓ into two subsets, each of size at least 5 and not in convex position, then ℓ intersects the convex hull of some 5-hole in P. The proof of this result is computer-assisted.

Original languageEnglish
Article number105236
Number of pages31
JournalJournal of Combinatorial Theory, Series A
Volume173
DOIs
Publication statusPublished - Jul 2020
Externally publishedYes

Keywords

  • Empty k-gon
  • Empty pentagon
  • Erdös–Szekeres type problem
  • Planar point set
  • k-Hole

Fingerprint

Dive into the research topics of 'A superlinear lower bound on the number of 5-holes'. Together they form a unique fingerprint.

Cite this