# 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$?

• By the way you wrote it, $N$ has to be $L\cdot\frac{k}{a}$. Do you mean that the degrees are at most $k$ and $a$? – R B Feb 24 '15 at 15:57
• I want the degrees to be exactly $k$ and $a$. Does $N=Lk/a$ guarantee that all pairs of vertices of $U$ have at least one common neighbour? – Cantfindname Feb 24 '15 at 16:04
• You asked for the value of $N$. This doesn't make much sense if $N$ has only one possible value. Also, in your second formulation of the problem, $k$ doesn't appear. – R B Feb 24 '15 at 16:11
• @RB Thanks for your interest, if you have an answer for the second formulation please post it. – Cantfindname Feb 25 '15 at 14:04

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<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<L^2e^{-N(\frac{a}{L})^2}$$

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

\begin{align} L^2e^{-N(\frac{a}{L})^2}<1\\ -N(\frac{a}{L})^2<-2\ln L\\ N>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})$.