Consider a separating union-closed family $\mathcal{F}$ of $n$ finite sets with $\mathcal{F} \not = \{ \emptyset \}$.

Let $U(\mathcal{F})$ be the union of all sets in $\mathcal{F}$ (the universe). Let $q = |U(\mathcal{F})|$.

Separating means that for any two elements $x,y$ in the universe there exist $A \in \mathcal{F}$ such that $x \in A$ and $y \not\in A$, or $x \not\in A$ and $y \in A$.

Let $S = \{ |A \Delta B| : A,B \in \mathcal{F}, A \not= B \}$ be the set of all sizes of symmetric differences between any two sets in $\mathcal{F}$ (Hamming distances).

I have run many tests on example families and always found $S = [m] = \{1, 2, \ldots, m-1, m\}$ with $m \le q$.

I have thought about $|A \Delta B| = |A \Delta (A \cup B)|+|B \Delta (A \cup B)|$, but that doesn't seem to help much.

Can we prove that $S = [m]$, or find a counterexample?


1 Answer 1


Checking more carefully, I have found that this answer can be used as a counterexample here as well, since $S = [21] \setminus \{18\}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.