<p>This is an upper bound on $N$ for the second formulation:</p>

<p>Assume that I pick $N$ uniformly random sets.</p>

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

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

<p>Using the union bound, the chance that <em>some</em> pair will not be covered is at most:</p>

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

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

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

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

<p>\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}</p>

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

<p>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$$</p>

<p>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).</p>

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

CC BY-SA 3.0
2015-02-25T16:28:57.447Z
2015-02-25T18:49:11.597Z
2015-02-25T18:49:11.597Z
R B
<p>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.</p>

<p>A different formulation of my problem is the following:</p>

<p>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: <a href="http://en.wikipedia.org/wiki/Set_cover_problem" rel="nofollow">http://en.wikipedia.org/wiki/Set_cover_problem</a> (right?), but is there an easier/faster way to calculate the minimum number without calculating the sets, given $L$ and $a$?</p>

CC BY-SA 3.0
2015-02-24T15:57:31.350Z
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
CC BY-SA 3.0
2015-02-24T16:04:12.830Z
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
CC BY-SA 3.0
2015-02-24T16:11:36.367Z
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
CC BY-SA 3.0
2015-02-25T14:04:02.790Z
@RB Thanks for your interest, if you have an answer for the second formulation please post it.
Cantfindname
<graph-theory><set-cover><set-theory>
Minimum order of partite in a bipartite graph
Cantfindname
# Minimum order of partite in a bipartite graph

(Asked by: username_0 on 2015-02-24)

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

**Tags:** graph-theory, set-cover, set-theory
> **Comments:**
> **username_1**: 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$?  
> **username_0**: 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?  
> **username_1**: 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.  
> **username_0**: @RB Thanks for your interest, if you have an answer for the second formulation please post it.  

---

## 1 answers

### Answer by username_1 on 2015-02-25. Score: 2 | Accepted answer

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

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


---

