Prove that intersection of at least a pair of 3-member sets of {1, 2, ..., n} is equal to one.

Question

Suppose we have $n+1$ subsets with $3$ members from the set of numbers from $1$ to $n$. I wanna prove that the intersection of two of these subsets, is exactly one member.

My idea is to decompose subsets into $n$ sets named $a[1], a[2], ..., a[n]$ which each pair of sets in $a[i]$ have exactly $1$ member in common. Now, by the pigeonhole principle, we can prove the statement.

My other idea is to convert this problem to a graph. Graph $G$ has 2 parts $X$ and $Y$. Part $X$ consists of $n+1$ sets and part $Y$ consists of $n$ numbers (1 to n). Now, I draw an edge from each vertex in part $X$ to its members in part $Y$. So, we have to prove that there exists a pair of vertices $u, v\in X$ that the number of neighbors of $u$ and $v$ ($| N(u) \cap N(v)|$) is equal to one.

Thanks in advance for your help!

Answer 1

Here is an outline of a proof that seems to work (but there might be more elegant solutions).

1. Notation. Write $[n] = \{1,\ldots,n\}$, and let $\mathcal P([n]) = \{S : S \subseteq [n]\}$ be its power set. I will occasionally refer to the elements of $[n]$ as symbols.

2. Situation. Let $\mathcal S \subseteq \mathcal P([n])$ be a collection of $3$-element sets such that $|T_1 \cap T_2| \neq 1$ for all $T_1,T_2 \in \mathcal S$.

3. Definition. Let $\mathcal S$ be as in Situation 2. Define $G_{\mathcal S} = (V,E)$ to be the graph given by $V = \mathcal S$ and $E = \{\{T_1,T_2\} : T_1 \cap T_2 \neq \varnothing\}$. In other words, $V$ has a vertex for every $3$-element set in $\mathcal S$, and two sets/vertices $T_1,T_2 \in \mathcal S$ are connected if $T_1$ and $T_2$ intersect. (Note: if $T_1$ and $T_2$ are adjacent in $G_{\mathcal S}$, then $|T_1 \cap T_2| = 2$.)

4. Claim. If $\mathcal S$ is as in Situation 2, then $G_{\mathcal S}$ is a disjoint union of cliques.

Proof. Let $T_1T_2\cdots T_k$ be a path in $G_{\mathcal S}$ with $T_1 \neq T_k$. Then $|T_1 \cap T_k|$ is either $0$ or $2$.

Suppose $|T_1 \cap T_k| = 0$. Let $i$ be the least index such that $|T_i \cap T_k| \neq 0$. Then $|T_i \cap T_k| \geq 2$, by the assumption on $\mathcal S$ (cf. Situation 2). But $T_i$ contains only one element (i.e. symbol) which is not contained in $T_{i-1}$, so we also have $|T_{i-1} \cap T_k| > 0$: a contradiction. We conclude that $|T_1 \cap T_k| = 2$, so $T_1$ and $T_k$ are connected by an edge. $\quad\Box$

5. Claim. The only possible cliques in $G_{\mathcal S}$ are of the form $\{\{a,b,c_1\},\{a,b,c_2\},\{a,b,c_3\},\ldots\}$, or a subset of $\{\{a,b,c\},\{a,b,d\},\{a,c,d\},\{b,c,d\}\}$.

Proof. Suppose that $\mathcal C \subseteq \mathcal S$ is a clique in $G_{\mathcal S}$. Choose two subsets $T_1,T_2 \in \mathcal C$, which are necessarily of the form $T_1 = \{a,b,c\}$ and $T_2 = \{a,b,d\}$. Let $T_3 \in \mathcal C$ be distinct from $T_1$ and $T_2$. We distinguish two cases.

• If $T_3$ contains both $a$ and $b$, then we claim that $\mathcal C$ is of the form $\{\{a,b,c_1\},\{a,b,c_2\},\{a,b,c_3\},\ldots\}$. Indeed, write $T_3 = \{a,b,e\}$, and let $T_k \in \mathcal C$ be different from $T_1$, $T_2$, and $T_3$. If $T_k$ does not contain $a$, then $|T_1 \cap T_k| = 2$ forces $b,c \in T_k$; $|T_2 \cap T_k| = 2$ forces $b,d \in T_k$; and $|T_3 \cap T_k| = 2$ forces $b,e \in T_k$. But now $|T_k| \geq 4$, which is a contradiction. Analogously, $T_k$ must contain $b$, so every $T_k \in \mathcal C$ contains $a$ and $b$.

• If $T_3$ does not contain both $a$ and $b$, then $|T_1 \cap T_3| = |T_2 \cap T_3| = 2$ forces $T_3 = \{a,c,d\}$ or $T_3 = \{b,c,d\}$. By rearranging $a$ and $b$, we may assume without loss of generality that $T_3 = \{a,c,d\}$. Let $T_k \in \mathcal C$ be different from $T_1$, $T_2$, and $T_3$. Then $$ |T_k \cap \{a,b,c\}| = |T_k \cap \{a,b,d\}| = |T_k \cap \{a,c,d\}| = 2, $$ so the only remaining possibility is $T_k = \{b,c,d\}$. $\quad\Box$

6. Proposition. If $\mathcal S$ is as in Situation 2, then $|\mathcal S| \leq n$.

Proof. For every clique $\mathcal C$ in $G_{\mathcal S}$ one has $|\mathcal C| \leq \big|\bigcup_{T\in\mathcal C} T\big|$, by Claim 5. (In words: every clique uses at least as many symbols $a,b,c,\ldots \in [n]$ as it has vertices.) Since $G_{\mathcal S}$ is a disjoint union of cliques, and since different cliques use different symbols, it follows that $|\mathcal S| \leq n$. $\quad\Box$

Answer 2

Let us write the $n$-element ground-set $S$ as $S=\{1,2,\ldots, n\}$ and let us write the $n+1$ sets as $x_1,x_2, \ldots, x_{n+1}$; then each $x_j$ is a 3-element subset of $S$. Furthermore, let us write $Y=\{x_1,x_2,\ldots, x_{n+1}\}$

Let $W$ be any subset of $Y$. Then we write as ${\cal{N}}(W)$ the integers $i \in S$ such that there is a $x \in S$ such that $i \in S$.

We make the following claims:

Claim 1: For any proper subset $U$ of $S$ there is at least one $x_j$ s.t. $1 \le |x_j \cap U| \le 2$, lest we are done.

Indeed, then there are $b$ elements $x$ of $Y$ s.t. $x \subseteq U$ and there are $n+1-b$ elements $x$ s.t. $x \subseteq S \setminus U$. Writing $|U|=a$ with $a$ positive and less than $n$, if $a<b$ then we can finish using induction. If $a \ge b$ then $|S \setminus U| = n-a < n+1-b$ so we can use induction here as well. $\surd$

Now let us fix a set $x_1 \in Y$. And let us write $x_1=\{1,2,3\}$. By Claim 1 we can order $Y$ s.t. there is some integer $j' \ge 2$ s.t. each of $x_2,\ldots x_{j'}$ intersects $x_1$, and $x_{j'+1}$ does not, if $j'$ satisfies $j'<n+1$ that is. Now, we may assume that each of $x_2,\ldots x_{j'}$ intersects $x_1$ at exactly 2 elements in the ground-set, lest we are done [$x_{j+1}$ and $x_{j+2}$ cannot share 3 elements lest they are the same set]. We make the following claim:

Claim 2: Let us use the notation in the above paragraph. Let $A_1$ be the set of $x_j$ that intersect $x_1$ at precisely $\{1,2\}$; $A_2$ be the set of $x_j$ that intersect $x_1$ at precisely $\{2,3\}$; and $A_3$ the set of $x_j$ that intersect $x_1$ at precisely $\{1,3\}$, and let us assume WLOG that $|A_1| \ge |A_2| \ge |A_3|$. Then by Claim 1, $A_1 \cup A_2 \cup A_3$ is nonempty. Also, lest we are done, if $A_2 \cup A_3$ is nonempty then $|A_1| = 1$, and so $|A_1 \cup A_2 \cup A_3| \le 3$.

Indeed, let us suppose that $x_2,x_3 \in A_1$. Then one can write $x_2=\{1,2,4\}$ and $x_3=\{1,2,5\}$. Then any $x \in A_2 \cup A_3$ will satisfy either $|x \cap x_2|=1$, or $|x \cap x_3|=1$. And so Claim 2 follows. $\surd$

Claim 3: Let us assume that $|A_1 \cup A_2 \cup A_3| \le 3$. Then let us define $U$ to be the following subset of $S$: $$U=\{i: i \in x {\text{ for some }} x \in A_1 \cup A_2 \cup A_3 {\text{ or }} i=1,2,3\}.$$ Let $x_{j'+1} \in Y$ s.t. $1 \le |x_{j'+1} \cap W| \le 2$. Then: (i) $U \le 6$ and so is a proper subset of $S$ (ii) $x_{j'+1}$ exists by Claim 1 (iii) $x_{j'+1}$ does not intersect $x_1=\{1,2,3\}$ (iv) $x_{j'+1}$ intersects at least one $x \in A_1 \cup A_2 \cup A_3$ at exactly one element in $S$ [because each $x \in A_1 \cup A_2 \cup A_3$ contains exactly one element in $U \setminus \{1,2,3\}$].

Claim 4. Let us assume that $|A_1 \cup A_2 \cup A_3| \ge 4$. Then as in Claim 3 let us write $$U=\{i: i \in x {\text{ for some }} x \in A_1 \cup A_2 \cup A_3 {\text{ or }} i=1,2,3\}.$$ Then (i) $A_2 \cup A_3$ is empty [by Claim 2] (ii) $|A_1| \le n-3$ (iii) Each $x \in A_1$ is of the form $\{1,2,i\}$; $i \ge 4$. (iv) Let $x'$ be any element in $Y \setminus A_1$ that also is not $x_1$. [Such an $x'$ exists by (ii).] If $U$ is a proper subset of $S$ let us assume that $1 \le |x \cap U| \le 2$ otherwise $x \subset U$. Then $|x' \cap x =1|$ for at least one $x \in A_1 \cup A_2 \cup A_3$.

We now show (iv). Let us write $x'=\{i_1,i_2,i_3\}$. Then each of $i_1,i_2,i_3 \ge 4$ because $x' \not = x_1$ and $x' \not \in A_1$ and so $x' \not \in A_1 \cup A_2 \cup A_3$ by (i).

However, by definition of $U$, there is an $x \in A_1$ such that $i_1 \in x$ and so by (iii) of the claim, $x=\{1,2,i\}$. So $|x' \cap x|=1$. $\surd$

Claims 3 and 4 exhaust the possibilities, so the result follows.

Answer 3

There is a well-known problem (sometimes referred to as the "Oddtown" problem) generalizing this one: if you have a family of subsets of $\{1,2,\dots,n\}$ such that

• each subset has odd size, and
• any two subsets have even intersection,

then there can be at most $n$ of them. The proof is by linear algebra. Take $\mathbf x_1, \mathbf x_2, \dots \in \mathbb F_2^n$ to be the indicator vectors of these sets over $\mathbb F_2$. Then the first condition says that $\mathbf x_i \mathbin{\boldsymbol{\cdot}} \mathbf x_i = 1$ for all $i$, and the second condition says that $\mathbf x_i \mathbin{\boldsymbol{\cdot}} \mathbf x_j = 0$ for all $i \ne j$.

Then the vectors form an "orthonormal" basis of $\mathbb F_2^n$, where I put the word "orthonormal" in quotes because the usual dot product isn't an inner product here. Still, the proof that the vectors form a basis is the same as in $\mathbb R^n$, and means that there can be at most $n$ of them (the dimension of $\mathbb F_2^n$).

---

From here, it follows that if you have a family of $n+1$ subsets of $\{1,2,\dots,n\}$ such that every subset has size $3$, they can't all have even intersection. The only possible odd intersection is an intersection in only one element.