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}\}$.
$\begingroup$
$\endgroup$
4
-
$\begingroup$ There is Harper's isoperimetric bound in Hamming cube (estimate size of the neighborhood via size of the set), but I do not know about isodiametric problem (maximal size of the set with given diameter). $\endgroup$– Fedor PetrovCommented Sep 29, 2015 at 10:16
-
$\begingroup$ Just want to clarify two things: (1) $l$ is given and fixed and we want to find the optimal $\mathcal{F}$ of that size, right? (2) The definition of $N(\mathcal{F})$ is correctly written "for all $A \in \mathcal{F}$"? (It shouldn't be "for some $A \in \mathcal{F}$"?) $\endgroup$– usulCommented Sep 29, 2015 at 11:33
-
1$\begingroup$ Assuming that's right, since $N(\mathcal{F})$ is the intersection of the Hamming balls of size $k$ around each $A \in \mathcal{F}$ minus $\mathcal{F}$, surely $\mathcal{F}$ must be as "clumped" as possible? (i.e. a Hamming ball when $l$ is the correct size). For instance, if we decrease the distance of some $A \in \mathcal{F}$ to every other $B \in \mathcal{F}$, then we only increase $|N(\mathcal{F})|$. $\endgroup$– usulCommented Sep 29, 2015 at 11:35
-
$\begingroup$ We also hope that this will happen. Is there any way to prove your statement. $\endgroup$– Francis Raj SCommented Sep 29, 2015 at 11:50
Add a comment
|