For positive integers $\ell < m < n$, consider a partition of $[2n]$ into two $n$-element sets $(X,Y)$. How many ways are there to choose an $m$-subset $A \subset [2n]$ such that the size of the intersection $A \cap X$ is at least $\ell$?
I believe this quantity is given by the following sum: $$ S_{\ell,m,n} := \sum_{j=0}^{m-\ell}{n \choose m-j} {n \choose j}. $$
If my reasoning is correct, is there a way to obtain a non-trivial upper bound (i.e. approximation) for $S_{\ell,m,n}$?
I agree with your formula. You choose $j \in \{0,\ldots,m-\ell\}$ (it will be the cardinal of $A \cap Y$, and given such a $j$ you choose independently $j$ elements in $Y$ and $m-j$ elements in $X$.
Here is an upper bound
$$S_{\ell,m,n} \le \sum_{j=0}^{m} {n \choose m-j} {n \choose j} = {2n \choose m}.$$
One obtains the last equality by looking at the coefficient of $X^m$ in the product $(1+X)^n \times (1+X)^n$. My guess is that this bound is sharp when $m/2-\ell >> \sqrt{m}$.
Less trivial bound
The quotient $S_{\ell,m,n}/{2n \choose m}$ is the probability $\mathbf{P}[X \ge \ell]$ where $X$ is a random hypergeometric random variable with parameters $2n$, $n$ and $m$. The law of $X$ is symmetric with regard to $m/2$ and is less spread out than the binomial law with parameters $m$ and $1/2$ (sampling without replacement provides a least dispersion of the number of success).
More precisely, given binomial random variable $Y$ with parameters $m$ and $1/2$, I guess that when $\ell \ge m/2$, $$2\mathbb{P}[X \ge \ell] = \mathbb{P}[|X-m/2| \ge \ell-m/2] \le \mathbb{P}[|Y-m/2| \ge \ell-m/2] = 2\mathbb{P}[Y \ge \ell].$$ Does anyone have a reference or a proof of this fact? Then, Cramer-Chernoff inequalities give nice bounds.
