4
$\begingroup$

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.

1 Answers 1

2

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.