extremal bipartite graph 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
 A: 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. 
A: 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.
