Let $d \in \mathbb{N}$ even, and let's consider the bipartite graph $G_d$ that has nodes labeled on the left side by $\{x \in \{0,1\}^d : |x| = d/2\}$ and on the right side by $\{x \in \{0,1\}^d : |x| = d/2 + 1\}$. Two nodes are connected if their corresponding labels differ in only one position, i.e., when $d = 4$, then nodes $0011$ and $0111$ are connected by an edge. If it helps, one can consider $G_d$ as all edges that are present in a cut through the Hamming cube of dimensions $d$, between all vertices with weight $d/2$ and $d/2+1$.
Now, let's consider particular subgraphs of this graph. To that end, take $0 \leq k \leq d$ even, and fix $k/2$ bits in a $d$-bit string to be $1$ and $k/2$ others to be $0$. Restrict $G_d$ to just the nodes whose labels agree on these $k$ bits. We refer to these subgraphs as $k$-bit subgraphs. For example, if $d = 4$ and we fix the last two bits to be $01$, then the only nodes remaining are $0101$ and $1001$ on the left side, and $1101$ on the right side.
Finally, suppose that in the original graph $G_d$, we remove a constant fraction of the edges (for concreteness let's say a third). What is the smallest $k$ for which we can ensure that we can still recover a $k$-bit subgraph from this sparser original graph (even when we remove thes edges from $G_d$ in the worst possible way)?
Observations:
- The number of edges in $G_d$ is $\binom{d}{d/2} \cdot \frac{d}{2}$: there are $\binom{d}{d/2}$ nodes on the left side, and each has $d/2$ neighbors.
- The number of edges in a $k$-bit subgraph is $\binom{d-k}{(d-k)/2} \cdot \frac{d-k}{2}$, for the same reasons.
- The number of possible choices for $k$-bit subgraphs is $\binom{d}{k} \cdot \binom{k}{k/2}$. This is because one has to choose $k$ bits to fix, and subsequently $k/2$ bits to fix with $1$ amongst those.
My attempts:
Sure enough, when $k = d$, then restricting to a $k$-bit subgraph from $G_d$ only retains $1$ node, so retaining such a graph from the sparser original graph is always possible too.
When $k = 0$, then restricting to a $k$-bit subgraph retains all edges, which cannot possibly be a subgraph of the sparser graph.
With a crude counting argument, one can show that for $k = d-2$, it is also always possible to find a $k$-bit subgraph from the sparser graph. The idea is that with some symmetry argument, every edge in $G_d$ can be found to be present in $$\frac{2 \binom{d}{d-2} \cdot \binom{d-2}{d/2-1}}{\frac{d}{2} \cdot \binom{d}{d/2}}$$ $(d-2)$-bit subgraphs, which means that after removing $1/3 \cdot \binom{d}{d/2} \cdot \frac{d}{2}$ edges from $G_d$, there is still a positive number of $(d-2)$-bit subgraphs remaining.
However, I am stuck at all intermediate values for $k$, I'm not sure how to proceed. Any hint, even as faint as how to approach the problem, would be greatly appreciated.