# Ramsey-type questions in geometric settings

## ABSTRACT

A graph is called {\em $H$-free} if it does not contain $H$ as an induced subgraph. Erdos and Hajnal raised the following question. Is it true that for every graph $H$ there exists $\varepsilon(H)>0$ with the property that any $H$-free graph with $n$ vertices contains either a complete or an empty subgraph with $n^{\varepsilon(H)}$ vertices? We answer this question in the affirmative for some special classes of graphs, including graphs defined by geometric means.

Speaker's Contact Info: pach(at-sign)CIMS.NYU.EDU