MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
For the lower bound, there are $r$-partite graphs satisfying your property, where each class has size $2k$ and $K_{k,k}$ is the best we can do. To see this, let $X_1, \dots, X_r$ be the vertex classes. For $i \in [r-1]$, make $X_i$ complete to $X_{i+1}$ (but remove a perfect matching). Then put a perfect matching between $X_r$ and $X_1$. – Tony Huynh Mar 26 '12 at 6:39
up vote 3 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.