# Maximum number of subsets of $\{1,2,\dots,n\}$ of cardinalities $1, \ldots, \ell$ that are not included in each other

Given a natural number $$n \ge 4$$, what is the maximum number $$\ell$$ of subsets $$A_1,A_2,\ldots, A_\ell$$ of $$\{1,2,\ldots,n\}$$ satisfying:

1. $$A_i$$ contains exactly $$i$$ elements for $$1 \le i \le \ell$$.
2. None of the subsets $$A_i$$ is included in any other.

I tried small examples but I don't see the pattern.

Any ideas are welcome.

• What results do you get for small $n$? – lulu Dec 14 '19 at 0:03
• Unless I'm mistaken I found $n = 4$ >> $l=2$ and $n=5$ >> $l = 3$ and $n=6$ >> $l = 3$ – ahmed Dec 14 '19 at 0:07
• For $n=6$ what's wrong with the chain $(1), (2,3), (3,4,5), (2,4,5,6)$? – lulu Dec 14 '19 at 0:10
• @chittychitty $(1)$,$(2,3)$, $(2,4,5)$ seems to be a maximal chain – ahmed Dec 14 '19 at 0:13
• where does the question come from? – Bart Michels Dec 15 '19 at 15:32

## 2 Answers

For $$n \geq 4$$, the maximum is $$n-2$$.

Clearly, $$\ell \geq n-1$$ is impossible: wlog $$A_1 = \{1\}$$ and $$A_2 = \{2, 3\}$$. Because $$\ell \geq n-1 \geq 3$$, we have $$\ell \neq 1, 2$$ and hence $$1 \notin A_\ell$$ and wlog $$2 \notin A_\ell$$. So $$\ell = |A_\ell| \leq n-2$$.

We can obtain $$\ell = n-2$$ as follows: For $$1 \leq k \leq n/2$$, define $$A_k = \{2, 4, \ldots, 2(k-1) \} \cup \{2k-1\}$$ and $$A_{n-1-k} = \{2, 4, \ldots, 2(k-1) \} \cup \{2k+1, 2k+2, \ldots, n \}$$ (If $$n$$ is odd and $$k = \frac{n-1}2$$, both of the above choices work.) It is easy to check none of these sets includes another.

One can come up with these sets as follows: wlog $$A_1 = \{1\}$$.

All other $$A_k$$ must not contain $$1$$. Thus wlog $$A_{n-2} = [3, n]$$.

All other $$A_k$$ must not contain $$1$$, and must contain $$2$$ (otherwise they are a subsetof $$A_{n-2}$$). Thus wlog $$A_2 = \{2, 3\}$$.

All other $$A_k$$ must not contain $$1$$ and must contain $$2$$ but not $$3$$. Thus wlog $$A_{n-3} = \{2 \} \cup [5, n]$$.

All other $$A_k$$ must not contain $$1$$ nor $$3$$, and must contain $$2$$ and $$4$$ (otherwise they are a subset of $$A_{n-3}$$). Thus wlog $$A_3 = \{2, 4, 5\}$$.

All other $$A_k$$ must contain $$2$$ and $$4$$, but not $$1$$ nor $$3$$ nor $$5$$. Thus wlog $$A_{n-4} = \{2, 4 \} \cup [7, n]$$. And so on.

That is, up to permutation the choice of $$A_k$$ above is the only one: there are $$n!$$ possibilities.

Let the maximum $$l$$ for some $$n$$ be given by $$l_n$$.

The first thing to note is that $$l_n \leq n-2$$ for all $$n\geq 4$$ as the element in $$A_1$$ cannot be in $$A_{l_n}$$ and atmost one of the two elements in $$A_2$$ can be in $$A_{l_n}$$.

Now, we shall prove that $$l_n = n-2$$ for all $$n\geq 4$$.

We have that $$l_4=2$$ as we have $$A_1=\{1\},A_2=\{2,3\}$$ as a solution.

Also, $$l_5=3$$ as we have $$A_1=\{1\}, A_2=\{2,3\}$$ and $$A_3=\{2,4,5\}$$ as a solution.

For $$n\geq 6$$, let $$l_k=k-2$$ for all $$k\leq n$$.

Let $$A_1=\{1\}$$. Let $$A_{n-2}=\{3,4,\cdots,n\}$$. Now, let $$3=1'$$, $$4=2'$$ and so on. (Rename $$i+2$$ as $$i'$$ for $$1\leq i\leq n-2$$).

We can find $$n-4$$ subsets $$A'_i, 1\leq i\leq n-4$$ satisfying the given conditions for $$\{1',2',3',\cdots,(n-2)'\}.$$

Finally, let $$A_k=\{2\}\cup A'_{k-1}$$.

We have this as a solution as:

1. $$\{1\}\not\subseteq A_i$$ for $$i\geq 1$$
2. $$A_k\not\subseteq A_{n-2}$$ for $$2\leq k\leq n-3$$ as $$2\in A_k$$ but $$2\not\in A_{n-2}$$.
3. $$A_i\not\subseteq A_j$$ for $$2\leq i as we have defined the $$A_i$$'s in terms of a previous solution in such a way that no subset is contained in another. (We have used the fact that $$l_{n-2}=n-4$$)

As we have $$l_5=3$$ and $$l_6=4$$, $$l_n = n-2$$ for all $$n\geq 4$$.

For example, take $$n=6$$.

We have $$A_1 = \{1\}$$, $$A_2=\{2\}\cup \{1'\}=\{2,3\}$$, $$A_3=\{2\}\cup\{2',3'\}=\{2,4,5\}$$ and $$A_4=\{3,4,5,6\}.$$