# Union of sets having $\binom{n - 1}{2}$ elements with each two of them having $n - 2$ common elements has cardinality of at least $\binom{n}{3}$.

Let $$S_1, S_2, \dots, S_n$$ sets that have each of them $$n - 1 \choose 2$$ elements, with $$n - 2$$ common elements for each two of them. Prove that their union has at least $$n \choose 3$$ elements. Find an example for equality case.

Let us examine the simplest case $$n = 3$$. Each of them has $$2 \choose 2$$ $$= 1$$ elements and each two of them have $$1$$ element in common, so, in fact, the three sets are identical, so their union has exactly $$3 \choose 3$$ $$= 1$$. (Equality case confirmed)

Examining $$n = 4$$, each set should have $$3 \choose 2$$ $$= 3$$ elements and $$2$$ in common every $$2$$. We may construct $$\{a, b, c\}$$, $$\{a, b, d\}$$, and the last set may be $$\{a, b, e\}$$ or $$\{a, c, d\}$$, both of them satsifying the conditions.

However, I am unable to generalize the problem

• for the equality case, just take $S_i$ to be the set $\{s\subseteq[n]:|s|=3,i\in s\}$. Commented Mar 9, 2022 at 14:25
• In case it might help: if $k$ is the number of elements of the union of $S_1,S_2,\ldots,S_n$, then each element will occur in $S_1,S_2,\ldots,S_n$ on average $n\binom{n-1}{2}/k$ times. If $k \lt \binom{n}{3}$, then $n\binom{n-1}{2}/k > 3$, therefore there will be at least one element belonging to at least $4$ sets. From that, maybe we can deduce that $k \ge \binom{n}{3}$, I don't know how though. Commented Mar 9, 2022 at 16:24
• These sets are called a "$t$-intersecting family" (here $t=n-2$). We can get an upper bound on the union by noting that there $n{n \choose 2}$ elements counting duplicity and we have overcounted by at least the sizes of $|S_1\cap S_2|,\dots,|S_1\cap S_n|=n-2$ i.e. by $(n-1)(n-2)$, so the union has cardinality $\le \frac{(n-1)(n-2)^2}{2}$. We can attain this upper bound with $S_1\cap S_2\cap \cdots \cap S_n=\{1,2,\dots,n-2\}$ and every other element of $S_1,\dots,S_n$ occurring once only.
– A.M.
Commented Mar 11, 2022 at 13:45
• Another thing in case it might help. Let $x_j$ be the number of elements belonging to exactly $j$ sets. We have $\sum_{j=1}^n{jx_j} = n\binom{n-1}{2} = 3\binom{n}{3}$. If I am correct, I think we have also $\sum_{j=2}^n{\binom{j}{2}x_j} = \binom{n}{2}(n-2) = 3\binom{n}{3}$. And finally we seek to show that the two above equalities together with $\sum_{j=1}^n{x_j} \lt \binom{n}{3}$ don't give any solution. Commented Mar 11, 2022 at 14:15
• @BillyJoe For $n \le 100$, the minimum $\sum_j x_j$ subject to those two constraints is indeed $\binom{n}{3}$. Commented Mar 11, 2022 at 14:53

We will do some double counting. Let $$S_1\cup S_2\cup \ldots \cup S_n=\{b_1,\ldots, b_k\}$$. Our goal is to prove that $$k\geq\binom{n}{3}$$.

Let $$x_i$$ be the number of sets in which $$b_i$$ appears. Then $$x_1+\ldots+x_k=\sum_{i=1}^{n}|S_i|=n\binom{n-1}{2}$$ and $$\sum_{i=1}^{k}\binom{x_i}{2}=\sum_{1\leq i \leq j} |S_i \cap S_j|=(n-2)\binom{n}{2}.$$ All is left to do is to use Jensen's inequality (or CBS) for the convex function $$f(x)=\binom{x}{2}$$. We have $$\sum_{i=1}^{k}\binom{x_i}{2}\geq k \binom{\frac{\sum x_i}{k}}{2}=\cfrac{(\sum x_i)(\sum x_i-k)}{2k}$$ and do the simplifications; note that $$n\binom{n-1}{2}=(n-2)\binom{n}{2}=3\binom{n}{3}$$.

Here is an alternative approach based on @BillyJoe's formulation. Let $$x_j$$ be the number of elements that appear in exactly $$j$$ sets. Then the two conditions in the problem imply the following two linear equality constraints: \begin{align} \sum_{j=1}^n j x_j &= n\binom{n-1}{2} = 3\binom{n}{3} \tag1 \\ \sum_{j=1}^n \binom{j}{2} x_j &= (n-2)\binom{n}{2} = 3\binom{n}{3} \tag2 \end{align} The total number of distinct elements is $$\sum_{j=1}^n x_j$$, which we want to show is at least $$\binom{n}{3}$$. First note that $$(j-2)(j-3) \ge 0$$, which is true for all integer $$j$$, is equivalent to $$1\ge \frac{2}{3}\cdot j-\frac{1}{3}\binom{j}{2}.\tag3$$ Now multiply $$(1)$$ by $$2/3$$ and $$(2)$$ by $$-1/3$$ and add them up to obtain $$\sum_{j=1}^n x_j \stackrel{(3)}{\ge} \frac{2}{3}\sum_{j=1}^n j x_j -\frac{1}{3}\sum_{j=1}^n \binom{j}{2} x_j \stackrel{(1),(2)}{=} \frac{2}{3}\cdot3\binom{n}{3} -\frac{1}{3}\cdot3\binom{n}{3} = \binom{n}{3}.$$ This lower bound is attained by taking $$x_3=\binom{n}{3}$$ and all other $$x_j=0$$.

One can use the following useful lemma: Let $$A_1,\dots,A_N$$ be $$r$$-element sets and $$X$$ be their union. If $$|A_i\cap A_j|\leq k$$ for all $$i\neq j$$, then $$|X|\geq \dfrac{r^2N}{r+(N-1)k}.$$

Proof: Let's introduce some convenient notation: $$[N]:=\{1,\dots,N\}$$ and for each $$x\in X$$ define $$d(x):=\#\{j\in [N]: x\in A_j\}.$$

For each $$1\leq i\leq N$$ consider $$\sum \limits_{x\in A_i}d(x)=\sum \limits_{x\in A_i}\sum \limits_{j=1}^N 1_{A_j}(x)=\sum \limits_{j=1}^N |A_i\cap A_j|=|A_i|+\sum \limits_{j\neq i}|A_i\cap A_j|\leq r+(N-1)k.$$ Summing over all sets $$A_i$$ we have $$\sum \limits_{i=1}^N \sum\limits_{x\in A_i}d(x)\leq rN+N(N-1)k.$$ However, the LHS of the inequalit can be written as follows: $$\sum \limits_{i=1}^N \sum\limits_{x\in A_i}d(x)=\sum \limits_{i=1}^N \sum\limits_{x\in X}1_{A_i}(x)\sum \limits_{j=1}^N 1_{A_j}(x)=\sum \limits_{x\in X}\left(\sum \limits_{i=1}^N 1_{A_i}(x)\right)^2=\sum \limits_{x\in X}d(x)^2\geq$$ $$\geq \frac{1}{|X|}\left(\sum \limits_{x\in X}d(x)\right)^2=\frac{1}{|X|}\left( \sum \limits_{i=1}^{N}|A_i|\right)^2=\dfrac{N^2r^2}{|X|}.$$ Hence we obtain: $$\dfrac{N^2r^2}{|X|}\leq rN+N(N-1)k \Leftrightarrow$$ $$|X|\geq \dfrac{r^2N}{r+(N-1)k}.$$

Remark: Your problem follows easily from that lemma: just take $$N=n, r=\binom{n-1}{2}$$ and $$k=n-2$$.