5
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I read it all. All I have to check now why is $d_i\geq 2$ for each $i$. $\endgroup$ – Aqua Jul 22 '18 at 19:55
  • $\begingroup$ If there is an element of $[n]$ contained in exactly in one of the $A_i$'s, say $1\in\{1,2,3\}$, then split $A_2,A_3,\ldots,A_n$ into two groups---those that contain $\{2,3\}$ and those that are disjoint from $\{2,3\}$. Now, if there are $k$ of those that contain $\{2,3\}$, then there are at most $n-k-3$ of those that are disjoint from $\{2,3\}$. Thus, you can end up with at most $1+k+(n-k-3)=n-2$ sets. $\endgroup$ – Batominovski Jul 22 '18 at 19:58
  • $\begingroup$ How you got $n-k-3$? $\endgroup$ – Aqua Jul 22 '18 at 20:07
  • $\begingroup$ The sets of the first kind must be of the form $\{2,3,t_1\},\{2,3,t_2\},\ldots,\{2,3,t_k\}$, and the sets of the second kind must be disjoint from $\{1,2,3,t_1,t_2,\ldots,t_k\}$. Therefore, the sets of the second kind are subsets of $[n]\setminus \{1,2,3,t_1,t_2,\ldots,t_k\}$, which has $n-k-3$ elements. $\endgroup$ – Batominovski Jul 22 '18 at 20:12
  • $\begingroup$ I still don't understand. Why does this mean that we have at most n-k-3 subsets? $\endgroup$ – Aqua Jul 22 '18 at 20:28
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.