Return to Answer

For all even $n \geq 16$, $N:=\binom{n/2}{2}$ is the right answer.

Semi-proof. Let $n=2k$ and observe that $4N=2k(k-1)$. Thus, if more than $N$ sets appear, then some element $x$ occurs in at least $k$ sets. Removing $x$ from these $k$ sets, we get a family of $3$-subsets of a set of size $2k-1$ which pairwise intersect in $1$ element. Now I think that for large $k$ this is not possible, although I am not an extremal set theorist. I would guess that for large $k$ the maximum size of such a family is achieved by taking a family of disjoint $2$-sets and adding the same point to each set. Such a family only has size $k-1$, which would be a contradiction.

Updated proof via Brendan McKay. I claim that for all even $n \geq 16$, $N$ is the right answer. From the semi-proof, it suffices to show that for any $k \geq 8$, the size of the largest family $\mathcal{F}$ of $3$-subsets of $[2k-1]$ (any two of which meet in exactly one point) is at most $k-1$. If $\mathcal{F}$ does not contain a triangle, this is true. So suppose, $123, 345, 561 \in \mathcal{F}$. If every member of $\mathcal{F}$ is contained in $[6]$ we are done. So there exists a set $F \in \mathcal{F}$ so that $F \cap [6] \neq \emptyset$. It follows that $|F \cap [6]|=1$, and by symmetry we may assume $F=174$. Now if all members of $\mathcal{F}$ are contained in $[7]$, then $\mathcal{F}$ is a subfamily of the Fano plane and we are done. Thus, there is a member $F'$ such that $|F' \cap [7]| =2$. Since the lines $123, 345$ and $174$ meet only at the point $1$, and $F'$ must contain a point from each of them, it follows that $1 \in F'$. But since these three lines also contain all points in $[7]$, $F'$ contains no other points of $[7]$. Thus, $|F'\cap [7]|=1$, a contradiction.

For all even $n \geq 16$, $N:=\binom{n/2}{2}$ is the right answer.

Semi-proof. Let $n=2k$ and observe that $4N=2k(k-1)$. Thus, if more than $N$ sets appear, then some element $x$ occurs in at least $k$ sets. Removing $x$ from these $k$ sets, we get a family of $3$-subsets of a set of size $2k-1$ which pairwise intersect in $1$ element. Now I think that for large $k$ this is not possible, although I am not an extremal set theorist. I would guess that for large $k$ the maximum size of such a family is achieved by taking a family of disjoint $2$-sets and adding the same point to each set. Such a family only has size $k-1$, which would be a contradiction.

Updated proof via Brendan McKay. I claim that for all even $n \geq 16$, $N$ is the right answer. From the semi-proof, it suffices to show that for any $k \geq 8$, the size of the largest family $\mathcal{F}$ of $3$-subsets of $[2k-1]$ (any two of which meet in exactly one point) is at most $k-1$. If $\mathcal{F}$ does not contain a triangle, this is true. So suppose, $123, 345, 561 \in \mathcal{F}$. If every member of $\mathcal{F}$ is contained in $[6]$ we are done. So there exists a set $F \in \mathcal{F}$ so that $F \cap [6] \neq \emptyset$. It follows that $|F \cap [6]|=2$, and by symmetry we may assume $F=174$. Now if all members of $\mathcal{F}$ are contained in $[7]$, then $\mathcal{F}$ is a subfamily of the Fano plane and we are done. Thus, there is a member $F'$ such that $|F' \cap [7]| =2$. Since the lines $123, 561$ and $174$ meet only at the point $1$, and $F'$ must contain a point from each of them, it follows that $1 \in F'$. But since these three lines also contain all points in $[7]$, $F'$ contains no other points of $[7]$. Thus, $|F'\cap [7]|=1$, a contradiction.

I think that for large even $n=2k$, maybe $N:=\binom{k}{2}$ is the right answer.

Semi-proof. Observe that $4N=2k(k-1)$. Thus, if more than $N$ sets appear, then some element $x$ occurs in at least $k$ sets. Removing $x$ from these $k$ sets, we get a family of $3$-subsets of a set of size $2k-1$ which pairwise intersect in $1$ element. Now I think that for large $k$ this is not possible, although I am not an extremal set theorist. I would guess that for large $k$ the maximum size of such a family is achieved by taking a family of disjoint $2$-sets and adding the same point to each set. Such a family only has size $k-1$, which would be a contradiction.

For all even $n \geq 16$, $N:=\binom{n/2}{2}$ is the right answer.

Semi-proof. Let $n=2k$ and observe that $4N=2k(k-1)$. Thus, if more than $N$ sets appear, then some element $x$ occurs in at least $k$ sets. Removing $x$ from these $k$ sets, we get a family of $3$-subsets of a set of size $2k-1$ which pairwise intersect in $1$ element. Now I think that for large $k$ this is not possible, although I am not an extremal set theorist. I would guess that for large $k$ the maximum size of such a family is achieved by taking a family of disjoint $2$-sets and adding the same point to each set. Such a family only has size $k-1$, which would be a contradiction.

Updated proof via Brendan McKay. I claim that for all even $n \geq 16$, $N$ is the right answer. From the semi-proof, it suffices to show that for any $k \geq 8$, the size of the largest family $\mathcal{F}$ of $3$-subsets of $[2k-1]$ (any two of which meet in exactly one point) is at most $k-1$. If $\mathcal{F}$ does not contain a triangle, this is true. So suppose, $123, 345, 561 \in \mathcal{F}$. If every member of $\mathcal{F}$ is contained in $[6]$ we are done. So there exists a set $F \in \mathcal{F}$ so that $F \cap [6] \neq \emptyset$. It follows that $|F \cap [6]|=1$, and by symmetry we may assume $F=174$. Now if all members of $\mathcal{F}$ are contained in $[7]$, then $\mathcal{F}$ is a subfamily of the Fano plane and we are done. Thus, there is a member $F'$ such that $|F' \cap [7]| =2$. Since the lines $123, 345$ and $174$ meet only at the point $1$, and $F'$ must contain a point from each of them, it follows that $1 \in F'$. But since these three lines also contain all points in $[7]$, $F'$ contains no other points of $[7]$. Thus, $|F'\cap [7]|=1$, a contradiction.

For even $n=2k$, one cannot get more than $N:=\binom{k}{2}$ sets.

Proof. Observe that $4N=2k(k-1)$. Thus, if more than $N$ sets appear, then some element $x$ occurs in at least $k$ sets. Removing $x$ from these $k$ sets, we get a family of $3$-subsets of a set of size $2k-1$ which pairwise intersect in $0$ or $1$ elements. However, the maximum size of such a family is $k-1$ (achieved by a pencil), which is a contradiction.

I think that for large even $n=2k$, maybe $N:=\binom{k}{2}$ is the right answer.

Semi-proof. Observe that $4N=2k(k-1)$. Thus, if more than $N$ sets appear, then some element $x$ occurs in at least $k$ sets. Removing $x$ from these $k$ sets, we get a family of $3$-subsets of a set of size $2k-1$ which pairwise intersect in $1$ element. Now I think that for large $k$ this is not possible, although I am not an extremal set theorist. I would guess that for large $k$ the maximum size of such a family is achieved by taking a family of disjoint $2$-sets and adding the same point to each set. Such a family only has size $k-1$, which would be a contradiction.