Maximum intersecting set families of $\{1,\ldots,n\}$

Question

Let $n\geq 3$ be an integer. We call a family ${\cal C}$ of subsets of $\{1,\ldots,n\}$ intersecting if it has the following properties:

1. $A, B\in {\cal C}$ implies $A\cap B \neq \emptyset$, and
2. $A \in {\cal C}, B\subseteq A$ implies $B\notin {\cal C}$.

One way to construct an intersecting family with a large number of elements is the following. For any positive integer $k$ we say ${\cal A}\subseteq {\cal P}(\{1,\ldots,k\})$ is an antichain if no member of ${\cal A}$ is contained in another member of ${\cal A}$. Let ${\cal M}$ be an antichain in ${\cal P}(\{1,\ldots,n-1\})$ with the maximum number of elements amongst all antichains in ${\cal P}(\{1,\ldots,n-1\})$. We denote this number by $m_{n-1}$. Let $${\cal C} = \big\{X\cup\{n\}: X\in {\cal M}\big\}.$$ So ${\cal C}$ is an intersecting family on $ \{1,\ldots,n\}$ with $m_{n-1}$ elements.

Question. Are there intersecting families on $ \{1,\ldots,n\}$ with more than $m_{n-1}$ elements?

Answer 1

The intersecting family in your example has $\binom{n-1}{\lfloor\frac{n-1}{2}\rfloor}$ members by Sperner's theorem. An example that achieves a larger value would be to take all the subsets of $[n]$ that have $1+\lfloor \frac{n}{2}\rfloor$ elements. This is best possible.

Milner proved that the largest size of a $k$-intersecting antichain in $\mathcal P([n])$ is $\binom{n}{\lfloor\frac{n+k+1}{2}\rfloor}$. Katona gave a simple proof of the case $k=1$ (the one relevant to the OP) in this paper.

Answer 2

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