6
$\begingroup$

I'm facing the following question:


Given a bipartite graph $G = (L \cup R, E)$.

Let $n = |L|$, $m = |R|$, and a parameter $k \in \mathbb{N}$, $n > m > k$.

What is a minimal possible number of edges in such a graph (in terms of $n,m,k$),

S.T.

For every subset $X \subset L$ of size $k$, $|N_G(X)| \geq k$ ?

(the size of the neighbourhood of $X$ is at least $k$)


Some comments:

  • I'm looking for a lower bound, any non-trivial bound will be very appreciated, even if not tight.
  • I suspect that the, if n < (k + 1)m, the answer is m + (n - m)k, any counter example will be welcomed.

Thank you

Gilad

$\endgroup$
5
  • $\begingroup$ The worst case is when there is a single $k$-element subset of $L$ for which the number of neighbors is $k-1$. So, the answer is $k+(n-k)m$. $\endgroup$
    – Boris Bukh
    Oct 29, 2015 at 14:30
  • $\begingroup$ You might consider adding the top-level tag co.combinatorics in order to make more people see this question; as questions cannot have more than 5 tags, you would need to replace one of the present tags. $\endgroup$
    – Stefan Kohl
    Oct 29, 2015 at 15:39
  • 1
    $\begingroup$ What does it mean "minimum required number of edges"? I see that people answer two different questions: 1)"what is a minimal possible number of edges in such a graph?" and 2)"what is a minimal $N$ such that a graph having at least $N$ edges satisfies this property?" $\endgroup$ Oct 29, 2015 at 17:05
  • $\begingroup$ Thank you all for your comments and answers. Just to clarify, I'm looking for a lower bound. One that is not tight, but non-trivial, will be very appreciated as well. $\endgroup$
    – Gilad
    Oct 30, 2015 at 6:04
  • 1
    $\begingroup$ What range of $m$ and $k$ are you looking for? For instance, $m\ge k^2$ is relatively easy if you don't mind a factor of $2$ in the answer, while $m-k=\sqrt k$, say, requires way more care. $\endgroup$
    – fedja
    Oct 31, 2015 at 1:19

2 Answers 2

2
$\begingroup$

Edit. My previous upper bound was not correct. Thanks to Gilad for pointing that out.

If $m<k$, then of course it is not possible. Otherwise, for an upper bound start with a matching $M$ saturating $R$ and let $L'$ be the vertices of $L$ saturated by $M$. Then pick a subset $K$ of size $k$ and add all edges from $L \setminus L'$ to $K$. This requires $m+k(n-m)$ edges. Note that there are different constructions that give the same bound. For example, if $n=\frac{k}{k-1}m$, then we can take a cycle $C$ of length $2m$ covering $R$ and then add a matching between the uncovered vertices of $L$ to $\frac{1}{k-1}m$ vertices of $R$ spaced equally apart by $C$.

Here is an example that shows that the upper bound of $m+k(n-m)$ is not always optimal. Take the complete graph $K_n$ and subdivide every edge once to obtain a bipartite graph with bipartition $(L,R)$. Note that $|L|=\binom{n}{2}$ and $|R|=n$. Also, every subset of $L$ of size $4$ has at least $4$ neighbours in $R$ (this corresponds to the fact that every $4$ edges in $K_n$ covers at least $4$ vertices. This graph only has $2\binom{n}{2}$ edges which is less than $n+4(\binom{n}{2}-n)$ for $n$ sufficiently large.

For the lower bound, you certainly require at least $n$ edges. Each of the $\binom{n}{k}$ $k$-subsets of $L$ must send at least $k$ edges to $R$. Each edge is counted $\binom{n-1}{k-1}$ times when we sum over the $k$-subsets of $L$. Thus, we require at least $k\binom{n}{k} / \binom{n-1}{k-1}=n$ edges.

$\endgroup$
3
  • $\begingroup$ If I understand correctly the first part of your answer, then I believe that it is not correct. Consider the following graph, then the neighbourhood of $\{l1, l3, l5\}$ is $\{r1, r3\}$. Am I missing something ? $\endgroup$
    – Gilad
    Nov 2, 2015 at 9:01
  • $\begingroup$ Oops. No, you are absolutely correct. Your conjectured answer may still be correct. Sorry about that. I edited my answer. $\endgroup$
    – Tony Huynh
    Nov 2, 2015 at 11:20
  • $\begingroup$ I think I found a different counter example to my conjecture, it might be true to some values of $n$ though. $\endgroup$
    – Gilad
    Nov 2, 2015 at 12:32
1
$\begingroup$

For $1\leq a\leq n$, $1\leq b\leq m$ denote by $f(n,m;a,b)$ the minimal possible number of edges in a bipartite graph $G=(L\sqcup R,E)$ such that $|L|=n$, $|R|=m$ and any $a$ vertices in $L$ have at least $m$ neighbors in $R$. Some observations:

1) (duality) $f(n,m;a,b)=f(m,n;m-b+1,n-a+1)$.

2) (partial values) $f(n,m;1,b)=nb$, $f(n,m;a,1)=n-a+1$, $f(a,m;a,b)=b$, $f(n,b;a,b)=b(n-a+1)$.

3) (recursive estimate based on hereditary property) if $n\geq a+1$, then $f(n,m;a,b)\geq f(n-1,m;a,b)+\lceil\frac{f(n-1,m;a,b)}{n-1}\rceil$. Indeed, let $v$ be a vertex of maximal degree $x$ in $L$. Then $G\setminus x$ satisfies the same property as $G$, hence $f(n,m;a,b)\geq x+f(n-1,m;a,b)$. On the other hand, some vertex in $L\setminus x$ has degree at least $\lceil\frac{f(n-1,m;a,b)}{n-1}\rceil$ by pigeonhole principle, thus $x\geq \lceil\frac{f(n-1,m;a,b)}{n-1}\rceil$.

4) (dual recursive estimate) $f(n,m;a,b)\geq f(n,m-1;a,b-1)+\lceil\frac{f(n,m-1;a,b-1)}{m-1}\rceil$.

To summarize, $f$ satisfies recursive inequality for $n>a$, $b>1$: $$ f(n,m;a,b)\geq \max\left(f(n-1,m;a,b)+\left\lceil\frac{f(n-1,m;a,b)}{n-1}\right\rceil,f(n,m-1;a,b-1)+\left\lceil\frac{f(n,m-1;a,b-1)}{m-1}\right\rceil\right). $$ Actually I won't be surprised if this is always equality. At least for similar Turan theorem such phenomenon takes place.

For example, they allow to get tight values $f(n,m;2,2)=n+\max(n-m,0)$. You may try to play further with small values of $a$ and $b$.

In any case, we may always use quick estimates based on average degrees in $L$: $f(n,m;a,b)\geq nb/a$ and in $R$: $f(n,m;a,b)\geq m(n-a+1)/(m-b+1)$. But upper integer parts in above recursive estimates are in general more precise.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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