extremal bipartite graph

Question

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

Answer 1

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.

Answer 2

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.