Let and let . Write Then Proof Let and . Define a bipartite graph by joining to if . Pick a random edge. The probability that it joins to is . It is also at most . So . lol Modified version Let also and define Let Assume that . Then Proof Pick a random pair , with . Then and adds random elements from . At worst, each element has probability to be in Thus we have But also this probability is at most (as has probability to be in ).