Maximum possible number of 1012-element subsets of {1,2,...,2024} such that no three intersect at more than one element

Question

I came across the following problem:

At most how many $1012$-element subsets of $\lbrace 1,2,\dots,2024 \rbrace$ may be chosen such that the intersection of any three subsets has at most one element?

I tried small cases. For example, I considered $3$-element subsets of $\lbrace 1,2,3,4,5,6 \rbrace$. By playing around (see table below), I think I got that for this case, the maximum is 8 subsets:

1	2	3	4	5	6
x	x	x
			x	x	x
x	x		x
	x	x		x
		x		x	x
x			x	x
x		x			x
	x		x		x

Essentially, we reach the point that for all triples $(a,b,c)$ at least one of $a-b, b-c, a-c$ are already in two subsets together. However, I have no idea how to prove that this is the maximum amount for even the $\lbrace 1,2,3,4,5,6 \rbrace$ case, and am stumped on how to proceed with the general or $2024$ case.

Intuitively, I feel as though there must be some way to upper-bound the number of subsets and then give a construction that satisfies that upper bound, but I am lost on how to proceed.

Any help would be greatly appreciated. Thank you!

Answer 1

For a given $n$, we want to find $n-$element subsets out of $[2n]$, such that the intersection of any 3 subsets is at most 1 element.

First, find 4 subsets such that the intersection of any 3 has $\leq 1$ elements in common.

Let $ A \cup B \cup C \cup D = [2n]$ with $|A| = |B| = \lfloor \frac{n}{2} \rfloor$ and $|C| = |D| = \lceil \frac{n}{2} \rceil$ be any partition of the appropriate size.
Take the 4 subsets: $A \cup C, A \cup D, B \cup C, B \cup D$.
Clearly the intersection of any 3 subsets is the emptyset.

Now, let's show that the maximum is indeed 4 for large $n$.
Suppose we have $k$ subsets that fulfills the condition.
Set up the standard incidence matrix, where the rows are the subsets and the columns are the elements.

Let's count column triples $\begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix}$.

Consider a column. Let there be $c_i$ 1's in it. We have $ \sum c_i = kn$ as the sum of the matrix.
The column contributes ${c_i \choose 3 }$ column-triples, so the total is $ \sum { c_i \choose 3}$.
By Jensen's inequality, we get $\sum { c_i \choose 3 } \geq 2n { \frac{ \sum c_i } { 2n } \choose 3 } = 2n { \frac{k}{2} \choose 3 }$.

Consider any 3 rows.
Since any 3 sets have an intersection of at most 1, these 3 rows can yield at most 1 column triple. Thus, there are at most ${k \choose 3 } $ triples.

Hence, $ 2n { \frac{k}{2} \choose 3 } \leq \text{ total column triples} \leq { k \choose 3 }$, or that $2n \leq \frac{ 8(k-1) } { (k-4) }$.
For $k = 5$, the RHS is $\frac{ 8 \times 5}{1} > 2 \times 1012$.
Thus, we have $k \leq 4$.

Thus, the maximum for $n \geq 21$ is 4.

---

BONUS

Note that for $n=3$, this argument doesn't work because we always have $6 \leq 8 \frac{ k-1}{k-4}$ for $k > 4$, and so we don't have a bound on $k$. Instead, we approach it in another manner, and count row pairs $(1, 1)$.

Each row has $n$ 1's, so there are ${n \choose 2}$ pairs. Since there are $k$ rows, so there are $ k { n \choose 2 } $ pairs.

Consider any 2 columns. Since any 3 sets have an intersection of at most 1, these 2 columns can yield at most 2 pairs of $(1, 1)$. Since there are ${2n \choose 2 }$ pairs of columns, thus there are at most $ 2 { 2n \choose 2 }$ such pairs.

Hence, $k { n \choose 2 } = \text{total pairs} \leq 2 {2n \choose 2 }$, or that $k \leq \frac{ 4(2n-1) } { n-1 } $.

Note that this is just an upper bound. It need not be achieved (hence may not be the maximum).

For $n =3$, we have $k \leq \frac{ 4 \times 5 } { 2 } = 10$.
I leave it to you to construct these 10 such subsets. Pursue your logic in the comments and build out from there. You can also use the fact that we have equality to make further deductions about the structure.

The equality conditions are:
Every element appears in exactly 3 subsets.
Every pair of elements appear in exactly 2 subsets.

$\{ 1, 2, 3\}, \{1, 3, 4 \}, \{1, 4, 5 \}, \{1, 5, 6 \}, \{1, 6, 2 \}, \{2, 3, 5 \} , \{ 3, 4, 6 \}, \{4, 5, 2 \}, \{ 5, 6 , 3 \}, \{ 6, 2, 4 \}$.

---

Notes

• In the comments, OP eventually came up with a much simpler argument for $n=6$.
  • If there are $\geq 11$ subsets, then one element (say $z$) must appear in at least $\lceil \frac{ 11\times 3}{6} \rceil = 6$ sets.
  • Consider the $6\times 2$ non-$z$ elements in these 6 sets. One element (say $y$) must appear in at least $\lceil \frac{12}{5} \rceil = 3$ sets. Then, the intersection of these 3 sets contains $ \{y, z \}$, which is a contradiction.
  • Note that this argument requires "knowing" that the answer is 10.
• What happens for $n = 4, 5, \ldots 20$? I'd love for you to investigate that.
• Small technicality/issue that is standard to deal with in such incidence matrix questions. Technically ${ x \choose 3 } = \frac{ x (x-1)(x-2) } {6}$ isn't convex in the $[0, 2]$ region, so we can't immediately Jensens it. Instead, what we actually use is the obviously convex function defined as

$${ x \choose 3 } = \begin{cases} 0 & x \leq 2 \\ \frac{x(x-1)(x-2) } { 6} & x > 2 \end{cases} $$