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}$.

Question

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

Answer 1

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}$.

Answer 2

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$.

Answer 3

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$.