Graph with large minimum degree can be union of few complete (bipartite) graphs

bipartite-graphsgraph theoryprobabilistic-method

Problem:

Let $G$ be a bipartite graph with $n$ vertices on each side and
minimum degree $n-d$. Show that it can be written as the union of
$O(d\log n)$ complete bipartite graphs.

My approach with the probabilistic method: consider a random algorithm that generates a complete bipartite graph (whose edges are a subset of $E(G)$. If we can show that each edge shows up with probability at least $\frac 1d$, then say I use $\lceil 3d\log n \rceil$ cliques. For each edge $e$, let $1_e$ be the indicator variable that it is not in all of the $\lceil 3d\log n \rceil$ cliques. Let $X$ be the number of edges not in the union. Then

$$\mathbb{E}[X] = \sum_e \mathbb{E}[1_e] \le \sum_e (1-1/d)^{3d \log n} \le n^2 (1-1/d)^{3d \log n} = n^2 e^{-3\log n} = \frac 1n < 1$$

So it is possible that $X=0$ i.e. we are done.

I tried the following algorithm which satisfies each edge showing up with probability at least $d^{-2}$: take a random ordering of the vertices. Let $uv$ be an edge of the graph, $S_u=V\backslash (u\cup N(u)), S_v=V\backslash (v\cup N(v))$, and $I$ be the set of vertices that come before all other vertices that are NOT adjacent to it. Then the events that $u\in I, v\in I$ are independent, and each happen with probability at least $\frac 1d$.

This is unfortunately not strong enough. Can I have a hint? Thank you!

Best Answer

Hints:

  1. When considering edges fails, it is natural to consider vertices.

  2. How do we find a complete bipartite subgraph of $G$? A natural algorithm is to choose a subset $A$ from one part, and let $B$ be the common neighbors of $A$. Then $(A,B)$ is a complete bipartite subgraph of $G$.

  3. Let $A$ be obtained by sampling each vertex on one side of $G$ with probability $p$. Then an edge $e = (a, b)$ lies in $(A, B)$ if and only if $a \in A$, and all the non-neighbors of $b$ does not lie in $A$. This happens with probability at least $p(1 - p)^d$. Taking $p = 1 / (d + 1)$, we see that each edge lies in $(A, B)$ with probability at least $1 / (e(d + 1))$.

  4. Finally, repeat this independently for $3e(d + 1) \log n$ times. Then each edge lies in none of the bipartite graphs with probability at most $n^{-3}$. Union bound, and finish.

Related Question