×

A Ramsey-type theorem for bipartite graphs. (English) Zbl 0978.05052

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\).

MSC:

05C55 Generalized Ramsey theory
PDFBibTeX XMLCite