Question

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.

Answer 1

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.