Ramsey-type questions in geometric settings

Janos Pach

Courant Institute, New York and Hungarian Academy of Sciences, Budapest

October 22,
refreshments at 3:45pm


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

Return to seminar home page

Combinatorics Seminar, Mathematics Department, MIT, sara(at-sign)math.mit.edu

Page loaded on September 21, 1999 at 02:59 PM. Copyright © 1998-99, Sara C. Billey. All rights reserved.