3
$\begingroup$

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.

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

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.

$\endgroup$
2
$\begingroup$

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<j\leq n-3$ 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\}.$

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