Return to Answer

Of your two properties, 1) is exactly the definition for what most people would call an intersecting family and 2) is exactly the definition of an antichain. So you are talking about maximum size intersecting antichains.

I'll write IF for intersecting family and MIF for maximal intersecting family (not properly contained in any other). I could also define mIF for maximal cardinality intersecting family. Clearly mIF implies MIF, but I will claim in a moment that mIF and MIF are equivalent. Note that MIF is with regard to some given universal set.

For antichains (AC) one could imagine various properties such as intersecting antichain (IAC), inclusion maximal antichain (MAC), maximum size antichain (mAC) along with the obvious MIAC and mAIC. You define $m_n$ as the size of an mAC for $[n]=\{1,2,\cdots,n\}.$ Let me also define $m^*_n$ as the size of a mIAC of $[n]$ You ask if a certain construction on such a mAC for $[n-1]$ gives a mIAC for $[n]$ and hence if $m_n^*=m_{n-1}.$ It turns out that the answer is

No. Your construction can be salvaged and it gives that $m^*_n=2m_{n-1}$ for odd $n$ and $m^*_n \lt 2m_{n-1}$ (but not by much) for even $n.$

That is a rather unsatisfactory statement because it reveals nothing about the families involved, and the answer is nice.

In brief:

• $\binom{2t+1}{t+1}=m_{2t+1}^*=2m_{2t}=2\binom{2t}{t+1}$ when $n=2t+1$ is odd
• $\binom{2t}{t+1}=m_{2t}^*=\binom{2t-1}t+\binom{2t-1}{t+1}=(2-\frac{2}{t+1})\binom{2t-1}t=(2-\frac{2}{t+1})m^*_{2t-1}$ when $n=2t$ is even.

In (too much) detail:

Interestingly, fun to prove (and mostly irrelevant to this question) are the following. But feel free to skim the definitions and jump past this list.

• Having $2^{n-1}$ elements is a sufficient condition for an IF to be an mIF.
• It is also necessary: any IF can be augmented to one of size $2^{n-1}.$
• So for an IF mIF,MIF and having $2^{n-1}$ members are all equivalent.
• Call a MAIC strong if it loses the property of being an IF when any one element is removed from any one member. The inclusion minimal members of a MIF are a strong MIAC but not usually an mIAC.
• The upset of a strong MIAC (its members and anything containing one of them) is a MIF.

Write $\binom{[n]}k$ for the family of $k$ element subsets of $[n]=\{1,2,\cdots n\}.$ This is always an AC and is a MIAC exactly if $2k \gt n.$

I'll write $12$ for $\{1,2\}.$ Then $\binom{[5]}4$ is a MIAC (of $[5]$) but not strong because it remains an IF (though not an antichain) if $\{2345\}$ is replaced by $\{345\}.$ On the other hand $\binom{[5]}3$ is is a MAIC even with regard to $[n]$ for $n \gt 5.$ It is also the unique mAIC of $[5].$

For $n=2t$ even, the unique largest AC has size $m_{2t}=\binom{2t}t$ and is $\binom{[2t]}t.$ It is not an IAC. But $\binom{[2t]}{t+1}$ is an IAC and, in fact the unique MAIC of $[2t].$ To get it, apply your move to $\binom{[2t-1]}t$ but also throw in the members of $\binom{[2t-1]}{t+1}.$

For $n=2t+1$ odd one has $m_{2t+1}=\binom{2t+1}t=\binom{2t+1}{t+1}$ realized by exactly two IF. The first is $\binom{[2t+1]}t$ and the other is $\binom{2t+1}{t+1}.$ The first is not an IF but the second is and is, in fact, the unique MIAC. To get it, apply your move to $\binom{[2t]}t$ but also throw in the members of $\binom{[2t]}{t+1}.$

Of your two properties, 1) is exactly the definition for what most people would call an intersecting family and 2) is exactly the definition of an antichain. So you are talking about maximum size intersecting antichains.

I'll write IF for intersecting family and MIF for maximal intersecting family (not properly contained in any other). I could also define mIF for maximal cardinality intersecting family. Clearly mIF implies MIF, but I will claim in a moment that mIF and MIF are equivalent. Note that MIF is with regard to some given universal set.

For antichains (AC) one could imagine various properties such as intersecting antichain (IAC), inclusion maximal antichain (MAC), maximum size antichain (mAC) along with the obvious MIAC and mAIC. You define $m_n$ as the size of an mAC for $[n]=\{1,2,\cdots,n\}.$ Let me also define $m^*_n$ as the size of a mIAC of $[n]$ You ask if a certain construction on such a mAC for $[n-1]$ gives a mIAC for $[n]$ and hence if $m_n^*=m_{n-1}.$ It turns out that the answer is

No. Your construction can be salvaged and it gives that $m^*_n=2m_{n-1}$ for odd $n$ and $m^*_n \lt 2m_{n-1}$ (but not by much) for even $n.$

That is a rather unsatisfactory statement because it reveals nothing about the families involved, and the answer is nice.

In brief:

• $\binom{2t+1}{t+1}=m_{2t+1}^*=2m_{2t}=2\binom{2t}{t+1}$ when $n=2t+1$ is odd
• $\binom{2t}{t+1}=m_{2t}^*=\binom{2t-1}t+\binom{2t-1}{t+1}=(2-\frac{2}{t+1})\binom{2t-1}t=(2-\frac{2}{t+1})m^*_{2t-1}$ when $n=2t$ is even.

In (too much) detail:

Interestingly, fun to prove (and mostly irrelevant to this question) are the following. But feel free to skim the definitions and jump past this list.

• Having $2^{n-1}$ elements is a sufficient condition for an IF to be an mIF.
• It is also necessary: any IF can be augmented to one of size $2^{n-1}.$
• So for an IF mIF,MIF and having $2^{n-1}$ members are all equivalent.
• Call a MAIC strong if it loses the property of being an IF when any one element is removed from any one member. The inclusion minimal members of a MIF are a strong MIAC but not usually an mIAC.
• The upset of a strong MIAC (its members and anything containing one of them) is a MIF.

Write $\binom{[n]}k$ for the family of $k$ element subsets of $[n]=\{1,2,\cdots n\}.$ This is always an AC and is a MIAC exactly if $2k \gt n.$

I'll write $12$ for $\{1,2\}.$ Then $\binom{[5]}4$ is a MIAC (of $[5]$) but not strong because it remains an IF (though not an antichain) if $\{2345\}$ is replaced by $\{345\}.$ On the other hand $\binom{[5]}3$ is is a MAIC even with regard to $[n]$ for $n \gt 5.$ It is also the unique mAIC of $[5].$

For $n=2t$ even, the unique largest AC has size $m_{2t}=\binom{2t}t$ and is $\binom{[2t]}t.$ It is not an IAC. But $\binom{[2t]}{t+1}$ is an IAC and, in fact the unique mIAC of $[2t].$ To get it, apply your move to $\binom{[2t-1]}t$ but also throw in the members of $\binom{[2t-1]}{t+1}.$

For $n=2t+1$ odd one has $m_{2t+1}=\binom{2t+1}t=\binom{2t+1}{t+1}$ realized by exactly two IF. The first is $\binom{[2t+1]}t$ and the other is $\binom{2t+1}{t+1}.$ The first is not an IF but the second is and is, in fact, the unique mIAC. To get it, apply your move to $\binom{[2t]}t$ but also throw in the members of $\binom{[2t]}{t+1}.$

What you call an intersecting family is typically called an intersecting antichain. The value and realization of your unspecified $m_n$ is well known.

Taking all subsets of size $k$ gives an antichain which is intersecting provided $n\lt 2k.$

For $n=2t$ even, the largest antichain has size $m_{2t}=\binom{2t}t$ and consists of the sets of size $t.$ It is not intersecting. The family of $t+1$ elements sets is an intersecting antichain, in fact the largest one.

For $n=2t+1$ odd one has $m_{2t+1}=\binom{2t+1}t=\binom{2t+1}{t+1}$ realized by taking all the $t$ element sets or all the $t+1$ element sets. Since the second of these two maximum size antichains is an intersecting antichain, that answers the question and we see that here $m_n\gt m_{n-1}.$

Returning to $n=2t$ the intersecting antichain has mentioned has size $2m_{n-1}.$

Of your two properties, 1) is exactly the definition for what most people would call an intersecting family and 2) is exactly the definition of an antichain. So you are talking about maximum size intersecting antichains.

I'll write IF for intersecting family and MIF for maximal intersecting family (not properly contained in any other). I could also define mIF for maximal cardinality intersecting family. Clearly mIF implies MIF, but I will claim in a moment that mIF and MIF are equivalent. Note that MIF is with regard to some given universal set.

For antichains (AC) one could imagine various properties such as intersecting antichain (IAC), inclusion maximal antichain (MAC), maximum size antichain (mAC) along with the obvious MIAC and mAIC. You define $m_n$ as the size of an mAC for $[n]=\{1,2,\cdots,n\}.$ Let me also define $m^*_n$ as the size of a mIAC of $[n]$ You ask if a certain construction on such a mAC for $[n-1]$ gives a mIAC for $[n]$ and hence if $m_n^*=m_{n-1}.$ It turns out that the answer is

No. Your construction can be salvaged and it gives that $m^*_n=2m_{n-1}$ for odd $n$ and $m^*_n \lt 2m_{n-1}$ (but not by much) for even $n.$

That is a rather unsatisfactory statement because it reveals nothing about the families involved, and the answer is nice.

In brief:

• $\binom{2t+1}{t+1}=m_{2t+1}^*=2m_{2t}=2\binom{2t}{t+1}$ when $n=2t+1$ is odd
• $\binom{2t}{t+1}=m_{2t}^*=\binom{2t-1}t+\binom{2t-1}{t+1}=(2-\frac{2}{t+1})\binom{2t-1}t=(2-\frac{2}{t+1})m^*_{2t-1}$ when $n=2t$ is even.

In (too much) detail:

Interestingly, fun to prove (and mostly irrelevant to this question) are the following. But feel free to skim the definitions and jump past this list.

• Having $2^{n-1}$ elements is a sufficient condition for an IF to be an mIF.
• It is also necessary: any IF can be augmented to one of size $2^{n-1}.$
• So for an IF mIF,MIF and having $2^{n-1}$ members are all equivalent.
• Call a MAIC strong if it loses the property of being an IF when any one element is removed from any one member. The inclusion minimal members of a MIF are a strong MIAC but not usually an mIAC.
• The upset of a strong MIAC (its members and anything containing one of them) is a MIF.

Write $\binom{[n]}k$ for the family of $k$ element subsets of $[n]=\{1,2,\cdots n\}.$ This is always an AC and is a MIAC exactly if $2k \gt n.$

I'll write $12$ for $\{1,2\}.$ Then $\binom{[5]}4$ is a MIAC (of $[5]$) but not strong because it remains an IF (though not an antichain) if $\{2345\}$ is replaced by $\{345\}.$ On the other hand $\binom{[5]}3$ is is a MAIC even with regard to $[n]$ for $n \gt 5.$ It is also the unique mAIC of $[5].$

For $n=2t$ even, the unique largest AC has size $m_{2t}=\binom{2t}t$ and is $\binom{[2t]}t.$ It is not an IAC. But $\binom{[2t]}{t+1}$ is an IAC and, in fact the unique MAIC of $[2t].$ To get it, apply your move to $\binom{[2t-1]}t$ but also throw in the members of $\binom{[2t-1]}{t+1}.$

For $n=2t+1$ odd one has $m_{2t+1}=\binom{2t+1}t=\binom{2t+1}{t+1}$ realized by exactly two IF. The first is $\binom{[2t+1]}t$ and the other is $\binom{2t+1}{t+1}.$ The first is not an IF but the second is and is, in fact, the unique MIAC. To get it, apply your move to $\binom{[2t]}t$ but also throw in the members of $\binom{[2t]}{t+1}.$

What you call an intersecting family is typically called an intersecting antichain. The value and realization Of your unspecified $m_n$ is well known.

Taking all subsets of size $k$ gives an antichain which is intersecting provided $n\lt 2k.$

For $n=2t$ even the largest antichain has size $m_{2t}=\binom{2t}t$ and consists of the sets of size $t.$ it is not intersecting. The family of $t+1$ elements sets is an intersecting antichain in fact the largest one.

For $n=2t+1$ odd one has $m_n=\binom{2t+1}t=\binom{2t+1}{t+1}$ realized by taking all the $t$ element sets or all the $t+1$ element sets. Since the second of these two maximum size antichains is an intersecting antichain, that answers the question and we see that here $m_n\gt m_{n-1}.$

Returning to $n=2t$ the intersecting antichain has mentioned has size $2m_{n-1}.$

What you call an intersecting family is typically called an intersecting antichain. The value and realization of your unspecified $m_n$ is well known.

Taking all subsets of size $k$ gives an antichain which is intersecting provided $n\lt 2k.$

For $n=2t$ even, the largest antichain has size $m_{2t}=\binom{2t}t$ and consists of the sets of size $t.$ It is not intersecting. The family of $t+1$ elements sets is an intersecting antichain, in fact the largest one.

For $n=2t+1$ odd one has $m_{2t+1}=\binom{2t+1}t=\binom{2t+1}{t+1}$ realized by taking all the $t$ element sets or all the $t+1$ element sets. Since the second of these two maximum size antichains is an intersecting antichain, that answers the question and we see that here $m_n\gt m_{n-1}.$

Returning to $n=2t$ the intersecting antichain has mentioned has size $2m_{n-1}.$