For $n \in \mathbb{N}$, let $\alpha_n$ be the biggest number such that there exist $\alpha_n$ subsets $M_1, \dots, M_{\alpha_n} \subseteq \{1, \dots, n\}$ with the property \begin{equation*} M_{i_1} \cup M_{j_1} \neq M_{i_2} \cup M_{j_2} \text{ if } \{i_1, j_1\} \neq \{i_2, j_2\} \end{equation*} for all $i_1, j_1, i_2, j_2 \in \{1, \dots, \alpha_n\}$. In other words, the pairwise unions of the $M_i$ and the $M_i$ themselves are all distinct.
What do we know about this number? From some numerical testing, I know that
- $\alpha_n = n$ for $n = 1, \dots, 5$
- $\alpha_6 = 7$
- $\alpha_7 \geq 9$
- $\alpha_8 \geq 10$
Is there a closed formula for this number? Are there lower or upper bounds? It is easy to see that $\lim_{n \to \infty} \alpha_n = \infty$ since $\alpha_n \geq n$. What is the order of this convergence?
EDITA very simple c++ program for brute-forceing the problem can be found here. I will commit some counterexamples (i.e. program output) in the future.
Frankl and Furedi, Union-free hypergraphs and probability theory, Europ J Combinatorics 5 (1984) 127-131, available here, says
Let $F(n)$ denote the maximum number of distinct subsets of an $n$-element set such that there are no four distinct subsets $A,B,C,D$ with $A\cup B=C\cup D$. We prove that $$2^{(n-\log3)/3}-2\le F(n)\le 2^{(3n+2)/4}$$ This isn't exactly the problem under discussion here, since Martin allows $A=B$, but I figure it's a good start. It might not be hard to adapt the methods and results of Frankl-Furedi to the problem at hand.
Note that there is a lot of room between the upper and lower bounds, between (essentially) $2^{n/3}$ and $2^{3n/4}$. This suggests to me that this is a hard problem, and some of the questions Martin asks may be open.
EDIT: Work on the problem did not stop in 1984. Coppersmith and Shearer, New bounds for union-free families of sets, Electron J Combin 5 (1998) Paper 39, MR1633846 (2000g:05140), calls a family, $F$, of subsets of an $n$-set weakly union-free if $F$ does not contain four distinct sets $A,B,C,D$ with $A\cup B=C\cup D$, and strongly union-free if, in addition, $A\cup B=A\cup C$ implies $B=C$. Then $f(n)$, the maximum size of a strongly union-free family, satisfies $$2^{(0.31349+o(1))n}\le f(n)\le2^{(0.4998+o(1))n}$$
Perhaps someone else will know whether there have been more recent improvements.