Number of subsets when each pair of distinct elements is contained in exactly one subset

Let $E$ be a set of cardinality $n$. Suppose $M_1, M_2, .. , M_m$ are
distinct proper subsets of $E$ such that for each pair of distinct elements $x_1, x_2\in E$, there is exactly one $M_i\supseteq\{x_1,x_2\}$. Prove that $m \ge n$.

It’s obvious $n$ has to be greater or equal to $3$. Also, for $n=3$, it’s easy to prove it, but I have no idea how to extend it. I think a proof using induction by $n$ is possible.

Solutions Collecting From Web of "Number of subsets when each pair of distinct elements is contained in exactly one subset"

Solution for general case

Let $E=\{1,2,\ldots, n\}$. Define column vectors $v_j=(v_{ij})^T$ with $v_{ij}= \mathbf{1}_{M_j}(i)$ which gives $1$ if $i\in M_j$ and $0$ otherwise. Then $M=(v_{ij})$ is an $n\times m$ matrix consisting of $0$, $1$ entries. Our goal is to prove that $\mathrm{rank}(M)=n$. We will show this by proving that the rows of $M$ are linearly independent. Then the columns $v_j$ form an spanning set for $\mathbb{R}^n$ and it will follow that $m\geq n$.

According to the assumptions, for each $i$, there are at least two sets $M_{j_1}$ and $M_{j_2}$ such that $i\in M_{j_1}\cap M_{j_2}$. Otherwise, the pairs $\{i,1\}$, $\ldots$, $\{i,n\}$ are all included in one set $M_k$ which gives $M_k=E$. Thus, we see that any row of $M$ contains at least two $1$’s.

Consider a $n\times n$ matrix $MM^T$. If $MM^T$ is nonsingular then the rows of $M$ are linearly independent. For the proof, let $M^T x = 0$ for some $x\in\mathbb{R}^n$. Then $MM^T x = 0$. Since $MM^T$ is nonsingular, $x=0$. Write the rows of $M$ as $R_1, \ldots , R_n$. Then $MM^T = (b_{ij})$ with the dot product $b_{ij}=R_i\cdot R_j$.

Since any row has at least two $1$’s, we have $b_{ii}\geq 2$. Since any pair $\{i, j\}$ with $i \neq j$ is in exactly one $M_k$, we have $b_{ij}=1$ for $i\neq j$. Writing the determinant as a multlinear function on columns, we obtain that $$\det MM^T \geq 1+n.$$
Therefore we conclude that $MM^T$ is nonsingular, and we are done.

Proof of the determinant inequality

Let $A=(a_{ij})$ be a $n\times n$ matrix with $a_{ij} = 1$ for $i\neq j$, and $a_{ii}\geq 2$. Then $\det A \geq 1+n$. For the proof, let $J=(1, 1, \ldots, 1)^T$, and write the determinant as a multilinear function on columns:
$$
\begin{align}
\det A &= \det \left((a_{11}-1) e_1 + J, \ldots, (a_{nn}-1)e_n + J\right)\\
&=\det \left((a_{11}-1)e_1, \ldots, (a_{nn}-1)e_n \right) \\ &+ \sum_{j=1}^n \det \left((a_{11}-1)e_1, \ldots, J (j-\textrm{th column}), \ldots, (a_{nn}-1)e_n \right)\\
&=\prod_{i=1}^n (a_{ii}-1) + \sum_{j=1}^n \frac{\prod_{i=1}^n (a_{ii}-1)}{a_{jj}-1}\geq 1 + n.
\end{align}$$

An Example for $n=4$

An example of such matrix $M$ is
$$
M=\begin{pmatrix} 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1
\end{pmatrix}, \ \ \
MM^T=\begin{pmatrix} 3 & 1 & 1 & 1 \\ 1 & 2 & 1 & 1 \\ 1 & 1 & 3 & 1 \\ 1 & 1 & 1 & 2 \end{pmatrix}, \ \ \ \det MM^T = 16.$$

Possibility of $m=n$

Note that it is possible to have $n$ distinct subsets $M_1, \ldots, M_n$ satisfying the requirements. Let $M_1=\{2,3,\ldots, n \}$, $M_2=\{1,2\}$, $M_3=\{1,3\}$, $\ldots$, $M_n = \{1, n\}$.

Here is a rather long proof.

From the condition, we find that for any two sets $M_i,M_j$ then $|M_i \cap M_j|\le 1$. Let $E= \{ 1,2, \cdots , n \}$ and $a_i \; (1 \le i \le n)$ be number of sets $M_j$ so that $i \in M_j$ then $a_i \ge 2$. Thus, $$\sum_{i=1}^n \binom{a_i}{2} = \sum_{1 \le i<j \le n}|M_i \cap M_j| = \binom m2-L,$$
where $L$ is number of pairs of sets $(M_i,M_j)$ so $|M_i \cap M_j|=0$.

Now, consider an arbitrary set $M_l= \{ x_1,x_2, \cdots , x_h \}$ then the total numbers of sets $M_j \; (1 \le j \le m)$ so that $|M_j \cap M_l| =1$ is $\displaystyle \sum_{i=1}^h a_{x_i}-|M_l|+1$. Thus, $\displaystyle \sum_{i=1}^h a_{x_i}-|M_l|+1=m-l_l$, where $l_i$ is number of sets $M_j$ so $|M_j \cap M_i|=0$.

Thus, similarly, by considering all set $M_i= \{ y_1, \cdots , y_l \}$ so that $1 \in M_i$ we find $\displaystyle \sum_{i=1}^l a_{y_i}-|M_i|+1 = m-l_i$. We add all of these to get
$$a_{1}^2+\sum_{i=2}^na_i – \sum_{1 \in M_i}|M_i|+a_1 = ma_1-\sum_{1 \in M_i} l_i, \qquad (1)$$
which is deduced from the fact that $|M_a \cap M_b| \le 1$ so in all $M_i \; (1 \in M_i)$ then if $j \in M_h \; (1 \in M_h, j \ne 1)$ then $j \not\in M_k \; (1 \in M_k, k \ne h)$. This also follows that $ \displaystyle \sum_{j \in M_i}|M_i|=a_j+n-1.$ Thus, $(1)$ is equivalent to $$a_1^2+\sum_{i=2}^na_i-n+1 = ma_1-\sum_{1 \in M_i} l_i.$$
Hence,
$$ \begin{array}{c} \displaystyle \sum_{i=1}^na_i^2+(n-1)\sum_{i=1}^na_i-n^2+n = m\sum_{i=1}^na_i-\sum_{i=1}^m|M_i|l_i,
\\ \displaystyle \sum_{i=1}^n (a_i^2-a_i)-n(n-1)+\sum_{i=1}^m|M_i|l_i = (m-n)\sum_{i=1}^na_i.
\\ \displaystyle (m-n)(m+n-1)-2L+\sum_{i=1}^m|M_i|l_i = (m-n)\sum_{i=1}^na_i,
\\ \displaystyle \sum_{i=1}^m|M_i|l_i-2L = (m-n) \left( \sum_{i=1}^na_i-m-n+1 \right). \end{array}$$

Since $\displaystyle\sum_{i=1}^ml_i=2L$ and $|M_i| \ge 2$ so $LHS \ge 2L \ge 0$. Hence, if $m<n$ then $\sum_{i=1}^na_i \le m+n-1$. But we also have $a_i \ge 2$ so $\displaystyle 2n \le \sum_{i=1}^na_i \le m+n-1$ implying $m \ge n+1$, a contradiction.

Thus, $m \ge n$.

Take $E = \{ x_1, x_2\}$.
There exist a set $M_{1,2}$ such that $x_1, x_2 \in M_{1,2}$.

But then $M_{1,2} = E$. This is a direct contradiction to the theorem.

Thus this doesn’t work for $n<3$.