Let $n>2$ be an integer and let $\ell \in\{1,2, \ldots, n\}$. A collection $A_{1}, \ldots, A_{k}$ of (not necessarily distinct) subsets of $\{1,2, \ldots, n\}$ is called $\ell$-large if $\left|A_{i}\right| \geq \ell$ for all $1 \leq i \leq k$. Find, in terms of $n$ and $\ell$, the largest real number $c$ such that the inequality
$$
\sum_{i=1}^{k} \sum_{j=1}^{k} x_{i} x_{j} \frac{\left|A_{i} \cap A_{j}\right|^{2}}{\left|A_{i}\right| \cdot\left|A_{j}\right|} \geq c\left(\sum_{i=1}^{k} x_{i}\right)^{2}
$$
holds for all positive integer $k$, all nonnegative real numbers $x_{1}, x_{2}, \ldots, x_{k}$, and all $\ell$-large collections $A_{1}, A_{2}, \ldots, A_{k}$ of subsets of $\{1,2, \ldots, n\}$.
The answer turns out to be
$$
c=\frac{n+\ell^{2}-2 \ell}{n(n-1)} .
$$

Throughout this solution, we work with vectors in $\mathbb{R}^{n^{2}}$. The entries will be indexed by ordered pairs $(p, q) \in\{1, \ldots, n\}^{2}$; the notation $\langle\bullet, \bullet\rangle$ denotes dot product, and $\|\bullet\|$ the vector norm.

Rewriting as a dot product. For $i=1, \ldots, n$ define $\mathbf{v}_{i}$ by
$$
\mathbf{v}_{i}[p, q]:=\left\{\begin{array}{ll}
\frac{1}{\left|A_{i}\right|} & p \in A_{i} \text { and } q \in A_{i} \\
0 & \text { otherwise }
\end{array} \quad \mathbf{v}:=\sum_{i} x_{i} \mathbf{v}_{i}\right.
$$

Then
$$
\begin{aligned}
\sum_{i} \sum_{j} x_{i} x_{j} \frac{\left|A_{i} \cap A_{j}\right|^{2}}{\left|A_{i}\right|\left|A_{j}\right|} & =\sum_{i} \sum_{j} x_{i} x_{j}\left\langle\mathbf{v}_{i}, \mathbf{v}_{j}\right\rangle \\
& =\left\langle\sum_{i} x_{i} \mathbf{v}_{i}, \sum_{j} x_{i} \mathbf{v}_{i}\right\rangle=\left\|\sum_{i} x_{i} \mathbf{v}_{i}\right\|^{2}=\|\mathbf{v}\|^{2} .
\end{aligned}
$$

ब Proof of the inequality for the claimed value of $c$. We define two more vectors $\mathbf{e}$ and $\mathbf{1}$; the vector $\mathbf{e}$ has 1 in the $(p, q)^{\text {th }}$ component if $p=q$, and 0 otherwise, while $\mathbf{1}$ has all-ones. In that case, note that
$$
\begin{array}{l}
\langle\mathbf{e}, \mathbf{v}\rangle=\sum_{i} x_{i}\left\langle\mathbf{e}, \mathbf{v}_{i}\right\rangle=\sum_{i} x_{i} \\
\langle\mathbf{1}, \mathbf{v}\rangle=\sum_{i} x_{i}\left\langle\mathbf{1}, \mathbf{v}_{i}\right\rangle=\sum_{i} x_{i}\left|A_{i}\right| .
\end{array}
$$

That means for any positive real constants $\alpha$ and $\beta$, by Cauchy-Schwarz for vectors, we should have
$$
\begin{aligned}
\|\alpha \mathbf{e}+\beta \mathbf{1}\|\|\mathbf{v}\| & \geq\langle\alpha \mathbf{e}+\beta \mathbf{1}, \mathbf{v}\rangle=\alpha\langle\mathbf{e}, \mathbf{v}\rangle+\beta\langle\mathbf{1}, \mathbf{v}\rangle \\
& =\alpha \cdot \sum x_{i}+\beta \cdot \sum x_{i}\left|A_{i}\right| \\
& \geq(\alpha+\ell \beta) \sum x_{i} .
\end{aligned}
$$

Set $\mathbf{w}:=\alpha \mathbf{e}+\beta \mathbf{1}$ for brevity. Then
$$
\mathbf{w}[p, q]=\left\{\begin{array}{ll}
\alpha+\beta & \text { if } p=q \\
\beta & \text { if } p \neq q
\end{array}\right.
$$
so
$$
\|\mathbf{w}\|=\sqrt{n \cdot(\alpha+\beta)^{2}+\left(n^{2}-n\right) \cdot \beta^{2}} .
$$

Therefore, we get an lower bound
$$
\frac{\|\mathbf{v}\|}{\sum x_{i}} \geq \frac{\alpha+\ell \beta}{\sqrt{n \cdot(\alpha+\beta)^{2}+\left(n^{2}-n\right) \cdot \beta^{2}}}
$$

Letting $\alpha=n-\ell$ and $\beta=\ell-1$ gives a proof that the constant
$$
c=\frac{((n-\ell)+\ell(\ell-1))^{2}}{n \cdot(n-1)^{2}+\left(n^{2}-n\right) \cdot(\ell-1)^{2}}=\frac{\left(n+\ell^{2}-2 \ell\right)^{2}}{n(n-1)\left(n+\ell^{2}-2 \ell\right)}=\frac{n+\ell^{2}-2 \ell}{n(n-1)}
$$
makes the original inequality always true. (The choice of $\alpha: \beta$ is suggested by the example below.)

Example showing this $c$ is best possible. Let $k=\binom{n}{\ell}$, let $A_{i}$ run over all $\binom{n}{\ell}$ subsets of $\{1, \ldots, n\}$ of size $\ell$, and let $x_{i}=1$ for all $i$. We claim this construction works.

To verify this, it would be sufficient to show that $\mathbf{w}$ and $\mathbf{v}$ are scalar multiples, so that the above Cauchy-Schwarz is equality. However, we can compute
$$
\mathbf{w}[p, q]=\left\{\begin{array}{ll}
n-1 & \text { if } p=q \\
\ell-1 & \text { if } p \neq q
\end{array}, \quad \mathbf{v}[p, q]=\left\{\begin{array}{ll}
\binom{n-1}{\ell-1} \cdot \frac{1}{\ell} & \text { if } p=q \\
\binom{n-2}{\ell-2} \cdot \frac{1}{\ell} & \text { if } p \neq q
\end{array}\right.\right.
$$
which are indeed scalar multiples, finishing the proof.