3
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .