Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

On 05.05.2017 at 12:20 in S6, there is the following noon lecture:

A superlinear lower bound on the number of 5-holes

Martin Balko

Abstract

(joint work with O, Aichholzer, T. Hackl, J. Kynčl, I. Parada, M. Scheucher, P. Valtr, and B. Vogtenhuber)

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(n(log n)^(4/5)), 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 l; into two subsets, each of size at least 5 and not in convex position, then l intersects the convex hull of some 5-hole in P. The proof of this result is computer-assisted.

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

Webmaster: kamweb.mff.cuni.cz         Modified: 19. 10. 2010