Here is a simple but important fact about bipartite graphs. Let be a bipartite graph with (finite) vertex sets and and edge density (meaning that the number of edges is ). Now choose uniformly at random from and uniformly at random from . Then the probability that all of and are edges is at least .

The proof is very simple. For each , let be the characteristic function of the neighbourhood of . That is, if is an edge and otherwise. Then is the sum of the degrees of the , which is the number of edges of , which is . If we set , then this tells us that . By the Cauchy-Schwarz inequality, it follows that .

But by the Cauchy-Schwarz inequality again,

That last expression is times the number of quadruples such that all of and are edges, and our previous estimate shows that it is at least . Therefore, the probability that a random such quadruple consists entirely of edges is at least , as claimed (since there are possible quadruples to choose from). (more…)