Ytukyg

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 $nto n+4$ works. Now I would like to prove that there is no such system if $4nmid n$.

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

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}_ninmathbb{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_kin{1,2,ldots,n}=:[n]$ with $j_1<j_2<ldots<j_k$. If $k<n$, then there exists $rin[n]$ such that $rneq 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}_rrangle=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 $jin A_i$. Then
$$sum_{j=1}^n,d_j=3n,.tag{#}$$

Note that $d_jgeq 2$ for all $jin[n]$.

From (*), we conclude that $d_jgeq 3$ for every $jin[n]$. However, (#) implies that $d_j=3$ for all $jin[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,zin[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.

Let $n$ be a positive integer. If $A_1,A_2,ldots,A_m$ are $3$-subsets of $[n]$ such that $left|A_icap A_jright|neq 1$ for $ineq j$, then the largest possible value of $m$ is
$$m_max=left{
begin{array}{ll}
n&text{if }nequiv0pmod{4},,\
n-1&text{if }nequiv1pmod{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}inmathbb{F}_2^n$ are linearly independent. Thus, there exists $mathbf{v}inmathbb{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_icap B$ has two elements. Observe that $X$ and $Y$ form a partition of ${1,2,ldots,n-1}$; moreover,
$$mathcal{X}:=bigcup_{iin X},A_itext{ and }mathcal{Y}:=bigcup_{iin Y},A_i$$
are disjoint subsets of $[n]$.

If $Xneq emptyset$, then we can use induction to finish the proof, noting that $A_isubseteq [n]setminus (Bcupmathcal{Y})$ for all $iin X$. From now on, assume that $X=emptyset$.

Consider a simple graph $G$ on the vertex set $B$ where two vertices $i,jin B$ ($ineq 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 $kin [n]setminus B$, then we say that $k$ is adjacent to $C$ if there exists $A_p$ such that $A_pcap B$ is an edge of $C$ and $kin 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_2in [n]setminus B$ are adjacent to $C_1$ and $C_2$, respectively, then $k_1neq 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 $jin[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 $jin[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).