Constructing trees in bipartite graphs (Q1918569): Difference between revisions

It is shown, that if \(G= (V, E)\) is a bipartite graph with more than \((a- 1)|Y|+ (b- 1)|X|- (a- 1)(b- 1)\) edges, where \((X, Y)\) is a vertex partition for \(G\) and \(a\leq b\) are natural numbers with \(a\leq |X|\), \(b\leq |Y|\), then \(G\) contains every tree \(T\) with bipartite numbers \(a\leq b\). This result is related to the Ramsey theory for trees. Let \(a\leq b\), \(T\) an \((a, b)\)-tree, \(G\) the complete bipartite graph with the vertex partition \((X, Y)\) such that \[ |X|= (a- 1) (k+ \sqrt{k(k- 1)}) + 1,\;|Y|= (b- 1) (k+ \sqrt{k(k- 1)})+ 1 \] and let \(\chi\) be an arbitrary coloring of the edges of \(G\) with \(k\) colors. Then \(G\) contains a monochromatic copy of \(T\).