Erdős, Paul; Hajnal, András; Pach, János A Ramsey-type theorem for bipartite graphs. (English) Zbl 0978.05052 Geombinatorics 10, No. 2, 64-68 (2000). Let \(H\) be a fixed graph on \(k\) vertices. The authors prove that every graph \(G\) on \(n\) vertices, which does not contain an indudced subgraph isomorphic to \(H\), has two distinct vertex sets, \(V_1\) and \(V_2\), each containing at least \(\lfloor(n/k)^{1/(k-1)}\rfloor\) vertices, so that either all of the edges between \(V_1\) and \(V_2\) belong to \(G\) or none of the edges between \(V_1\) and \(V_2\) belong to \(G\). This theorem has some interesting geometric implications including:There exists a positive constant \(\varepsilon\) such that every family \({\mathcal F}\) of \(n\) arcwise connected sets in the plane has two subfamilies \({\mathcal F}_1\) and \({\mathcal F}_2\) with at least \(n^\varepsilon\) members such that either every member of \({\mathcal F}_1\) intersects all members of \({\mathcal F}_2\) or no member of \({\mathcal F}_1\) intersects any member of \({\mathcal F}_2\). Reviewer: Jack E.Graver (Syracuse) Cited in 22 Documents MSC: 05C55 Generalized Ramsey theory Keywords:Ramsey-type theorem; bipartite graphs PDFBibTeX XMLCite \textit{P. Erdős} et al., Geombinatorics 10, No. 2, 64--68 (2000; Zbl 0978.05052)