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.

-
 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 2012 at 6:39 Could you add the [ramsey-theory] tag? – Zsbán Ambrus Mar 31 2012 at 18:00

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.

-