12
$\begingroup$

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

$\endgroup$
8
  • 3
    $\begingroup$ for the equality case, just take $S_i$ to be the set $\{s\subseteq[n]:|s|=3,i\in s\}$. $\endgroup$ Commented Mar 9, 2022 at 14:25
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Mar 9, 2022 at 16:24
  • $\begingroup$ 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. $\endgroup$
    – A.M.
    Commented Mar 11, 2022 at 13:45
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Mar 11, 2022 at 14:15
  • 2
    $\begingroup$ @BillyJoe For $n \le 100$, the minimum $\sum_j x_j$ subject to those two constraints is indeed $\binom{n}{3}$. $\endgroup$
    – RobPratt
    Commented Mar 11, 2022 at 14:53

3 Answers 3

4
$\begingroup$

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

$\endgroup$
3
+50
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .