Ramseytype questions in geometric settings
Janos Pach
Courant Institute, New York and
Hungarian Academy of Sciences, Budapest
October 22,
4:15pm
refreshments at 3:45pm
2338
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(atsign)CIMS.NYU.EDU
Return to seminar home page
Page loaded on September 21, 1999 at 02:59 PM.

Copyright © 199899, Sara C. Billey.
All rights reserved.

