Encuadernado con cubierta biclique

Question

Se trata de un problema de Extremal Combinatoria por Jukna que no puedo resolver yo mismo.

Primero algunos preliminares. Un biclique cobertura de un gráfico es una cubierta de un gráfico con completa bipartita de gráficos (de modo que cada borde de la inicial de la gráfica pertenece a al menos uno de los grafos bipartitos que cubrir la inicial de la gráfica). Para cada capa de un gráfico, deje que el peso de una cubierta de ser el número de vértices de cada uno de los subdiagramas (el bipartito gráficos) que se suman todos juntos. (es decir, si los gráficos $H_1, H_2, \dots, H_m$ son el bipartito gráficos que cubren $G,$, entonces el peso de la cubierta se $\displaystyle\sum_{i=1}^m |V(H_i)|,$ donde $|V(H_i)|$ indica el número de vértices en $H_i.$) cubrir con el mínimo peso como es $\text{bc}(G)$ para el gráfico de $G.$

Si $\mu_G$ es el mínimo por encima de todos los $(a+b)/ab$ para los pares de enteros $a,b \ge 1$ tal que $G$ contiene una copia completa de la bipartito gráfico: $a \times b$ (o $K_{a,b}$). Demostrar que $\text{bc}(G) \ge \mu_G \cdot |E|.$ (Donde $|E|$ indica el número de bordes de $G.$)

Muchas gracias por la ayuda.

Answer 1

Permita que$H_1$,$\ldots\,$,$H_m$ sea una portada de biclique arbitraria de$G$. Para cada$i$, deje$H_i \cong K_{a_i, b_i}$. Como$H_1$,$\ldots\,$,$H_m$ es una cobertura de$G$, tenemos $$ \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} $$ Reorganizar, tenemos$$\sum_{i=1}^m \lvert V_i \rvert \geq \mu_G \lvert E \rvert.$ $ Sin embargo, la portada$H_1$,$\ldots\,$,$H_m$ es arbitraria, por lo que tenemos$$\operatorname{bc}(G) \geq \mu_G \lvert E \rvert,$ $ como se indica.