There are $n$ different $3$-element subsets $A_1,A_2,...,A_n$ of the set $\{1,2,...,n\}$, with $|A_i \cap A_j| \not= 1$ for all $i \not= j$.

Question

Determine all possible values of positive integer $n$, such that there are $n$ different $3$-element subsets $A_1,A_2,...,A_n$ of the set $\{1,2,...,n\}$, with $|A_i \cap A_j| \not= 1$ for all $i \not= j$.

Source: China Western Olympiad 2010

---

Attempt:

It is quite clear that for $n=4k$ such a system exist. For $n=4$, we have $A_1 =\{1,2,3\}$, $A_2 =\{1,2,4\}$, $A_3 =\{2,3,4\}$, $A_4 =\{1,3,4\}$. It is not hard to see that induction $n\to n+4$ works. Now I would like to prove that there is no such system if $4\nmid n$.

I thought about linear algebra approach. Observe the given sets as vectors in $\mathbb{F}_2^n$. Then since $A_i\cdot A_i =1$ and $A_i\cdot A_j = 0$ for each $i\ne j$ these vectors are linear independent: $$ b_1A_1+b_2A_2+...+b_nA_n = 0\;\;\;\; /\cdot A_i$$ $$ b_1\cdot 0+b_2\cdot 0+...+b_i\cdot 1+...b_n\cdot 0 =0\implies b_i=0$$ But now, I'm not sure what to do...

Answer 1

Suppose that there are $n$ such sets $A_1,A_2,\ldots,A_n$, represented by indicator vectors $\mathbf{a}_1,\mathbf{a}_2,\ldots,\mathbf{a}_n\in\mathbb{F}_2^n$. Equip $\mathbb{F}_2^n$ with the usual inner product $\langle\_,\_\rangle$.

We already know that the vectors $\mathbf{a}_1,\mathbf{a}_2,\ldots,\mathbf{a}_n$ are linearly independent. Therefore, they span $\mathbb{F}_2^n$. Thus, the vector $\boldsymbol{1}:=(1,1,\ldots,1)$ can be written as $$\mathbf{a}_{j_1}+\mathbf{a}_{j_2}+\ldots+\mathbf{a}_{j_k}$$ for some $j_1,j_2,\ldots,j_k\in\{1,2,\ldots,n\}=:[n]$ with $j_1<j_2<\ldots<j_k$. If $k<n$, then there exists $r\in[n]$ such that $r\neq j_\mu$ for all $\mu=1,2,\ldots,k$. That is, $$1=\langle \mathbf{a}_r,\boldsymbol{1}\rangle =\sum_{\mu=1}^k\,\langle \mathbf{a}_{j_\mu},\mathbf{a}_r\rangle=0\,,$$ which is a contradiction. Therefore, $k=n$, whence $$\boldsymbol{1}=\sum_{j=1}^n\,\mathbf{a}_j\,.\tag{*}$$ Consequently, each element of $[n]$ belongs in an odd number of $A_1,A_2,\ldots,A_n$, whence at least one of the sets $A_1,A_2,\ldots,A_n$.

Furthermore, it is not difficult to show that every element of $[n]$ must belong in at least two of the $A_i$'s. (If there exists an element of $[n]$ belonging in exactly one $A_j$, then you can show that there are at most $n-2$ possible $A_i$'s.) Let $d_j$ be the number of sets $A_i$ such that $j\in A_i$. Then $$\sum_{j=1}^n\,d_j=3n\,.\tag{#}$$
Note that $d_j\geq 2$ for all $j\in[n]$.

From (*), we conclude that $d_j\geq 3$ for every $j\in[n]$. However, (#) implies that $d_j=3$ for all $j\in[n]$; i.e., every element of $[n]$ must be in exactly three of the $A_i$'s. Write $\mathbf{e}_1,\mathbf{e}_2,\ldots,\mathbf{e}_n$ for the standard basis vectors of $\mathbb{F}^n_2$. We see that $$\mathbf{e}_j=\mathbf{a}_p+\mathbf{a}_q+\mathbf{a}_r$$ where $j$ is in $A_p$, $A_q$, and $A_r$. This shows that $$A_p=\{j,x,y\}\,,\,\,A_q=\{j,y,z\}\,,\text{ and }A_r=\{j,z,x\}$$ for some $x,y,z\in[n]$. Since $x$ already belongs in $A_p$ and $A_r$, it must be belong in another $A_s$. Clearly, $A_s$ must be equal to $\{x,y,z\}$. From here, we conclude that the four elements $j,x,y,z$ belong in exactly four of the $A_i$'s, which are $\{j,x,y\},\{j,y,z\},\{j,z,x\},\{x,y,z\}$. The rest is easy.

Answer 2

Let $n$ be a positive integer. If $A_1,A_2,\ldots,A_m$ are $3$-subsets of $[n]$ such that $\left|A_i\cap A_j\right|\neq 1$ for $i\neq j$, then the largest possible value of $m$ is $$m_\max=\left\{ \begin{array}{ll} n&\text{if }n\equiv0\pmod{4}\,,\\ n-1&\text{if }n\equiv1\pmod{4}\,,\\ n-2&\text{else}\,. \end{array} \right.$$

Remark: Below is a sketch of my proof of the claim above. Be warned that a complete proof is quite long, whence I am providing a sketch with various gaps to be filled in. I hope that somebody will come up with a nicer proof.

Proof. The first two cases follow from my first answer. I shall now deal with the last case, where $m_\max=n-2$.

Suppose contrary that there are $A_1,A_2,\ldots,A_{n-1}$ satisfying the intersection condition. Then, proceed as before. The indicator vectors $\mathbf{a}_1,\mathbf{a}_2,\ldots,\mathbf{a}_{n-1}\in\mathbb{F}_2^n$ are linearly independent. Thus, there exists $\mathbf{v}\in\mathbb{F}_2^n$ such that $\mathbf{a}_1,\mathbf{a}_2,\ldots,\mathbf{a}_{n-1},\mathbf{b}$ form a basis of $\mathbb{F}_2^n$. We can assume that $\langle \mathbf{a}_i,\mathbf{b}\rangle=0$ for all $i=1,2,\ldots,n-1$ (otherwise, replace $\mathbf{b}$ by $\mathbf{b}-\sum_{i=1}^{n-1}\,\langle \mathbf{a}_i,\mathbf{b}\rangle \,\mathbf{a}_i$). Observe that $\langle \mathbf{b},\mathbf{b}\rangle=1$.

Note that $$\boldsymbol{1}=\sum_{i=1}^{n-1}\,\mathbf{a}_i+\mathbf{b}\,.$$ Let $B$ be the subset of $[n]$ with the indicator vector $\mathbf{b}$. Let $X$ denote the set of $i$ such that $A_i$ is disjoint from $B$, and $Y$ the set of $i$ such that $A_i\cap B$ has two elements. Observe that $X$ and $Y$ form a partition of $\{1,2,\ldots,n-1\}$; moreover, $$\mathcal{X}:=\bigcup_{i\in X}\,A_i\text{ and }\mathcal{Y}:=\bigcup_{i\in Y}\,A_i$$ are disjoint subsets of $[n]$.

If $X\neq \emptyset$, then we can use induction to finish the proof, noting that $A_i\subseteq [n]\setminus (B\cup\mathcal{Y})$ for all $i\in X$. From now on, assume that $X=\emptyset$.

Consider a simple graph $G$ on the vertex set $B$ where two vertices $i,j\in B$ ($i\neq j$) are connected by an edge iff $i$ and $j$ belongs in some $A_p$ simultaneously. If $C$ is a connected component of $G$ and $k\in [n]\setminus B$, then we say that $k$ is adjacent to $C$ if there exists $A_p$ such that $A_p\cap B$ is an edge of $C$ and $k\in A_p$, in which case, we also say that $A_p$ is incident to $C$. It is important to note that, if $C_1$ and $C_2$ are two distinct connected components of $G$, and $k_1,k_2\in [n]\setminus B$ are adjacent to $C_1$ and $C_2$, respectively, then $k_1\neq k_2$.

Let $C$ be a connected component of $G$ with at least two vertices. We have three probable scenarios:

1. $C$ is a type-1 connected component, namely, $C$ is an isolated edge (i.e., it has only two vertices and one edge);
2. $C$ is a type-2 connected component, namely, $C$ is a triangle (i.e., $C$ consists of $3$ vertices and $3$ edges);
3. $C$ is a type-3 connected component, namely, $C$ is a star graph (i.e., there exists a vertex $v$ of $C$ such that every edge of $C$ takes the form $\{v,w\}$, where $w$ is any vertex of $C$ distinct from $v$).

It can be readily seen that, if $C$ is a connected component of type 2 or type 3 of $G$, then $C$ is adjacent to exactly one element of $[n]\setminus B$. If $G$ has a connected component $C$ of type 2, then the removal of vertices in $C$ along with the element $j\in[n]\setminus B$ which is adjacent to $C$ reduces the elements of $[n]$ by $4$, whilst ridding of only three sets $A_i$. Then, we finish the proof for this case by induction. Suppose from now on that $G$ has no connected components of type 2.

Now, assume that $G$ has a connected component $C$ of type 3, which has $s$ vertices. Let $j\in[n]\setminus B$ be adjacent to $C$. Then, the removal of vertices of $C$ along with $j$ from $[n]$ reduces the elements of $[n]$ by $s+1$, whilst ridding of only $s-1$ sets $A_i$. Therefore, the claim hold trivially.

Finally, assume that $G$ has only connected components of type 1 and possibly some isolated vertices. Then, it follows immediately that there are at most $n-2t$ sets $A_i$, where $t$ is the number of connected components of type 1. This shows that $t=0$. Thus, $G$ has only isolated vertices, but this is a contradiction as well (as $X=\emptyset$ is assumed).