Algebraic Combinatorics Seminar

UNIVERSITY OF KENTUCKY
ALGEBRAIC COMBINATORICS SEMINAR
845 PATTERSON OFFICE TOWER
FALL 2005



"Empty convex hexagons"

Carlos Nicolas
University of Kentucky

Monday, October 17, 2005
3:00 pm, 845 Patterson Office Tower


Abstract:

Let P be a finite set of points in the plane, no three on a line. A subset S of P is an empty convex set of P if the interior of conv(S) contains no point of P. An empty convex 6-set of P is usually called an empty convex hexagon. Using the Erdös-Szekeres theorem we show that every set P with sufficiently many points contains an empty convex hexagon, giving an affirmative answer to a question posed by Erdös in 1977 that was open when I found my proof last semester. (Apparently someone in Europe has independently found a proof while I was typing my own.)