1

I'm looking for the answer of following problem: Find the maximal size of $S\subseteq 2^{[n]}$ such that there are no distinct $A,B,C\in S$ such that $A\cup B\not = C$. A possible construction is all set of odd size, which $\#S=2^{n-1}$. A possible construction is all set of size $\lfloor n/2\rfloor$, which $\#S={n\choose {\lfloor n/2\rfloor}}$. Is this maximal?

I've found https://arxiv.org/pdf/1601.03659.pdf. There is reference in that which Kleitman give an upper bound $(1+o(1)){n\choose {\lfloor n/2\rfloor}}$. Seemingly that's an open problem for an exact number.

Peter Wu
  • 817
  • 5
  • 15
  • All sets of odd size is not going to work in general. $A=\left{1,2,3\right}$ and $B=\left{1\right}$ have odd size but so does $A\cup B=A$. – Andijvie Sep 05 '22 at 07:31
  • @Andijvie yes I made a mistake here. I guess $n\choose{n/2}$ might be the correct answer – Peter Wu Sep 05 '22 at 07:40
  • 1
    The paper you reference defines a union-free family as a collection $F$ such that there are no three distinct sets $A,B,C\in F$ with $A\cup B=C$. This does not forbid the case $A\subset B=C$. Do you mean to use this definition too? – Karl Sep 05 '22 at 09:42
  • The families meeting the condition you've currently written are precisely the antichains with respect to set inclusion, so Sperner's theorem applies. – Karl Sep 05 '22 at 09:48
  • @Karl, yes I overlooked that, I should include this condition. – Peter Wu Sep 06 '22 at 01:57

0 Answers0