Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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

This concerns a problem from Extremal Combinatorics by Jukna that I cannot solve myself.

First some preliminaries. A biclique covering of a graph is a covering of a graph with complete bipartite graphs (so that every edge of the initial graph belongs to at least one of the bipartite graphs that cover the initial graph). For each such covering of a graph, let the weight of a covering be the number of vertices of each of the subgraphs (the bipartite graphs) all added together. (i.e. if the graphs $H_1, H_2, \dots, H_m$ are the bipartite graphs that cover $G,$ then the weight of this covering will be $\displaystyle\sum_{i=1}^m |V(H_i)|,$ where $|V(H_i)|$ denotes the number of vertices in $H_i.$) The covering with the minimum such weight is $\text{bc}(G)$ for the graph $G.$

If $\mu_G$ is the minimum over all the $(a+b)/ab$ for pairs of integers $a,b \ge 1$ such that $G$ contains a copy of the complete bipartite graph: $a \times b$ (or $K_{a,b}$). Prove that $\text{bc}(G) \ge \mu_G \cdot |E|.$ (Where $|E|$ denotes the number of edges of $G.$)

Thank you very much for the help.

share|cite|improve this question

Let $H_1$, $\ldots\,$, $H_m$ be an arbitrary biclique cover of $G$. For each $i$, let $H_i \cong K_{a_i, b_i}$. Because $H_1$, $\ldots\,$, $H_m$ is an edge cover of $G$, we have $$\begin{align} \lvert E \rvert &\leq \lvert E_1 \rvert + \cdots + \lvert E_m \rvert\\ &=\lvert V_1 \rvert \dfrac{a_1 b_1}{a_1 + b_1} + \cdots + \lvert V_m \rvert \dfrac{a_m b_m}{a_m + b_m}\\ &\leq \bigl(\lvert V_1 \rvert + \cdots + \lvert V_m \rvert \bigr) \max_{i} \biggl\{\dfrac{a_i b_i}{a_i + b_i}\biggr\}\\ &\leq \biggl(\sum_{i=1}^m \lvert V_i \rvert \biggr)\dfrac{1}{\mu_G}. \end{align}$$ Rearranging, we have $$\sum_{i=1}^m \lvert V_i \rvert \geq \mu_G \lvert E \rvert.$$ However, the cover $H_1$, $\ldots\,$, $H_m$ was arbitrary, so we have $$\operatorname{bc}(G) \geq \mu_G \lvert E \rvert,$$ as claimed.

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.