Minimum order of partite in a bipartite graph I want to create a bipartite graph where the first partite $U$ contains $L$ vertices with degree $k$ and the second partite $V$ contains $N$ other vertices with degree $a$. I need to find the minimum number of $N$ so that every pair of the $L$ vertices have a common neighbour.

A different formulation of my problem is the following:

Assume we have $L$ distinct numbers.
I want to calculate the minimum number of sets of size $a$ that are needed so that all unordered pairs of numbers are contained in at least one of the sets.
I understand that finding the sets is similar to the set cover problem: http://en.wikipedia.org/wiki/Set_cover_problem (right?), but is there an easier/faster way to calculate the minimum number without calculating the sets, given $L$ and $a$?
This is an upper bound on $N$ for the second formulation:

Assume that I pick $N$ uniformly random sets.

The probability of a pair of elements not to be covered by a specific set is
$$1-\left(\frac{a}{L}\right)^2$$

Therefore the chance that it is not covered by any set is:
$$\left(1-\left(\frac{a}{L}\right)^2\right)^N$$

Using the union bound, the chance that some pair will not be covered is at most:

$$P={L \choose 2}\left(1-\left(\frac{a}{L}\right)^2\right)^N$$

This means that if $P&lt;1$, there exists some proper covering using $N$ sets. Notice that:

$$P={L \choose 2}\left(1-\left(\frac{a}{L}\right)^2\right)^N&lt;L^2e^{-N(\frac{a}{L})^2}$$

Therefore it is enough to demand $L^2e^{-N(\frac{a}{L})^2}&lt;1$, which gives us a bound on $N$:

\begin{align}
L^2e^{-N(\frac{a}{L})^2}&lt;1\\
-N(\frac{a}{L})^2&lt;-2\ln L\\
N&gt;2\ln L\cdot(\frac{L}{a})^2
\end{align}

Which means that there exists a proper covering using $2\ln L\cdot(\frac{L}{a})^2$ sets of size $a$.

Now notice that every set covers $a\choose 2$ pair of elements, while $L\choose 2$ pairs exist, so a lower bound for $N$ would be:
$$\frac{L\choose 2}{a\choose 2}\approx (\frac{L}{a})^2$$

So the upper bound is tight up to factor $O(\log L)$. (If I had to bet, I'd say the lower bound is loose while the upper is asymptotically tight).

This means that if your goal is to compute the value of the optimal $N$ - answering $(\frac{L}{a})^2\sqrt{\log L}$ would give an approximation ratio of $O(\sqrt{\log L})$.