08/31/2007 - 16:30

08/31/2007 - 18:00

Speaker:

Louigi Addario-Berry

Location:

McConnell 320

Abstract:

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.