Large bicliques in r-partite graphs containing no independent sets having one vertex from each class 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.
 A: 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.
