1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – R B Feb 24 '15 at 15:57
  • $\begingroup$ 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? $\endgroup$ – Cantfindname Feb 24 '15 at 16:04
  • 1
    $\begingroup$ 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. $\endgroup$ – R B Feb 24 '15 at 16:11
  • $\begingroup$ @RB Thanks for your interest, if you have an answer for the second formulation please post it. $\endgroup$ – Cantfindname Feb 25 '15 at 14:04
2
$\begingroup$

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})$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.