Abstract:

A graph is called 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 epsilon(H)>0 with the property that any H-free graph with n vertices contains either a complete or an empty subgraph with n^{epsilon(H)} vertices? We answer this question in the affirmative for some special classes of graphs, including graphs defined by geometric means.

Coffee, Cookies, Company at the faculty lounge at 3:30.