On a geometric Ramsey-style problem.

08/31/2007 - 16:30
08/31/2007 - 18:00
Louigi Addario-Berry
McConnell 320
Given a point set P in R^2, the visibility graph V(P) is the graph with vertex set P and for which, given points p,q of P, pq is an edge precisely if the line segment [p,q] contains no points aside from p and q. In 2006, Kara, Por and Wood, conjectured that for all pairs of positive integers (k,c) there is a finite number v(k,c) such that if |P|> v(k,c) and no k points of P are collinear, then V(P) contains a clique of size c. Despite the simplicity of this statement, essentially no non-trivial bounds on v(k,c) are known. I will discuss some recent work on the conjecture of Kara et.al. This is joint work with Cristina Fernandes, Yoshiharu Kohayakawa, Jos Coelho de Pina, and Yoshiko Wakabayashi.
Last edited by on Mon, 08/27/2007 - 11:44