Let $G$ be a multipartite graph on $r$ classes, each containing $k$ vertices, such that there is no independent set which contains at least one vertex from each class. I believe such graphs contain a complete bipartite graph $K\_{f(k),f(k)}$ for each fixed $r$, with $f$ an increasing (possibly even linear) function, but the proof eludes me so far. Google search led me to extremely results about Ramsey-type results for bipartite subgraphs, but not complete ones. Any insights are much appreciated.



Large bicliques in r-partite graphs containing no independent sets having one vertex from each class
I believe I can prove this with a standard Ramsey-type argument, though *f* will grow slower than linear.


You'll need the following useful lemma.



> 
> Lemma 1 (bipartite Ramsey). For any natural numbers $ n\_0, n\_1, m\_0, m\_1 $, there exist natural numbers $ R\_0, R\_1 $ such that any bipartite graph with $ R\_0 $ upper and $ R\_1 $ lower vertices has either $ n\_0 $ upper and $ n\_1 $ lower vertices inducing a complete bipartite subgraph, or $ m\_0 $ upper and $ m\_1 $ lower vertices inducing an empty graph.
> 
> 
> 


Proof of lemma goes by induction. Choose an upper vertex *u*. If this vertex is linked to at least $ R\_1(n\_0 - 1, n\_1, m\_0, m\_1) $ lower vertices and there are enough upper vertices, then there's either a large empty induced subgraph, or a complete bipartite subgraph that's large enough if you include *u*. Similarly, if there are at least $ R\_1(n\_0, n\_1, m\_0 - 1, m\_1) $ lower vertices *u* is not linked to, you've won. Thus, 
$$
R\_1(n\_0, n\_1, m\_0, m\_1) := R\_1(n\_0 - 1, n\_1, m\_0, m\_1), + R\_1(n\_0, n\_1, m\_0 - 1, m\_1), 
$$
$$
R\_0(n\_0, n\_1, m\_0, m\_1) := 1 + \max(R\_0(n\_0 - 1, n\_1, m\_0, m\_1), R\_0(n\_0, n\_1, m\_0 - 1, m\_1))
$$
vertices are enough. The base case when $ n\_0 = 0 $ or $ m\_0 = 0 $ is trivial.


Now for the theorem you are asking for, we can prove like this.



> 
> Lemma 2. For any natural numbers $ r, f $, any simple pattern graph $P$ on the $r$ vertices $ 1, \dots, r $; there is a natural number $ k $ so that any large enough $ r $-partite graph $ G $ (one that has at least $ k $ vertices in each class) always contains either
> 
> 
> * a $ K\_{f, f} $ complete bipartite subgraph, or
> * vertices $ v\_1, \dots, v\_r $, one from each class respectively, such that for any $ i $ and $ j $, if $ i $ and $ j $ are linked in $ P $ then $ v\_i $ is not linked to $ v\_j $.
> 
> 
> 


The case where $ P $ is the complete graph gives the theorem you're asking for:



> 
> Theorem. For any natural numbers $ r, f $, there is a natural number $ k $ such that any large enough $ r $-partite graph $ G $ (with at least $ k $ vertices in each class) always contains either
> 
> 
> * a $ K\_{f, f} $ complete bipartite subgraph, or
> * vertices $ v\_1, \dots, v\_r $, one from each class respectively, that are pairwise unlinked.
> 
> 
> 


Proof of lemma 2 goes by fixing $ r, f $, then taking induction on $ P $. The base case when $ P $ is an empty graph is trivial: $ m $ vertices in each class of the bipartite graph is enough. 


Otherwise, suppose we already have the induction statement for pattern $ P' $, which is $ P $ with the edge $ {i, j} $ deleted, and we found that $ k' $ vertices per class is enough. We have a large enough graph $ G $ (with at least $ k $ vertices in each class, $ k $ is to be determined later) that does not contain a $ K\_{f,f} $ complete bipartite graph as a subgraph. We want to prove that $ G $ contains $ r $ vertices unlinked according to the pattern $ P $. 


Choose $ k = \max(R\_0(f, f, k', k'), R\_1(f, f, k', k')) $. Consider the induced subgraph of $ G $ made of only its classes $ i $ and $ j $. Both classes of this bipartite subgraph still has at least $ k $ vertices, and the subgraph still doesn't contain a $ K\_{f,f} $ complete bipartite graph. Thus, you can apply lemma 1 with $ n\_0 = n\_1 = f $ and $ m\_0 = m\_1 = k' $ to find that this subgraph has an empty induced subgraph formed of $ k' $ vertices from each of the two classes. Now let $ G' $ be the induced subgraph of $ G $ that contains the $ k' $ vertices from class $ i $ and $ k' $ vertices from class $ j $ as chosen above, and all vertices from all other classes. Thus, $ G' $ has no edges between class $ i $ and $ j $. By the induction statement, we can choose vertices $ v\_1, \dots, v\_r $ from each class of $ G' $ such that they are unlinked accoring to pattern $ P' $, but as $ v\_i $ and $ v\_j $ are also unlinked, these vertices are also unlinked according to pattern $ P $. QED.


