Combinatorics Seminar

When: Sunday, November 11, 10am Where: Schreiber 309 Speaker: Rom Pinchasi, Technion Title: On a problem by Grunbaum and Motzkin, and by Erdos and Purdy

Abstract:

Let P be a set of n blue points in the plane, not all collinear. Let G be a set of m red points disjoint from P such that every line determined by P contains a point from G. Grunbaum and Motzkin (1975) and independently Erdos and Purdy (1978) conjectured that m must be large in terms of n.

The fact that m>=cn for some constant c follows from the weak Dirac's theorem by Beck and by Szemeredi and Trotter (1983), where c is very small. No example is known with m less than n-6. This suggests that m>=cn for some reasonably large constant c.

We show that m>=(n-1)/3.