Skip to main content
3 of 3
changed mathbb to mathcal
domotorp
  • 19.1k
  • 3
  • 59
  • 128

Families of subsets with pairwise symmetric differences of cardinality at most $k$

Let $X$ be an $n$-element set and $\mathcal{F} \subseteq P(X)$ such that for all $A, B \in \mathcal{F}$, $|A△B| \leq k$ where $A△B$ denotes the symmetric difference of $A$ and $B$. Suppose $|\mathcal{F}| = l$ for some $2 \leq l \leq 2^{n−1}$, then for what kind of $\mathcal{F}$ will the $|N(\mathcal{F})|$ be maximum, where $N(\mathcal{F}) = \{C \in P(X)\backslash \mathcal{F} : |C△A| ≤ k$, for all $A ∈ \mathcal{F}\}$.