Theory of Combinatorial Algorithms, Institute of Theoretical Computer Science, Department of Computer Science, ETH Zürich

No Title

Ramsey-type questions in geometry

Janos Pach, City College New York and Hungarian Academy of Sciences

A graph is called H-free if it does not contain Has 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. In particular, we show that any family $\cal F$ of segments in general position in the plane has two disjoint subfamilies, each containing at least a fixed constant fraction of the members of $\cal F$ , such that either every member of the first subfamily crosses every member of the second, or no member of the first subfamily crosses any member of the second. This is an unpublished result of J. Solymosi and the speaker.

Back