Discrete Mathematics and Optimization Seminar

---

LOUIGI ADDARIO-BERRY
Oxford University
Friday August 31st at 4.30pm
McConnell 320



Title. On a geometric Ramsey-style problem.

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.