# Diameter of a set in the discrete cube

Let $$[n] = \{1, \dots, n\}$$.

Define the discrete cube $$Q_n$$ to be the graph with vertex set $$\mathcal{P}([n])$$ such that $$x,y \in \mathcal{P}([n])$$ are adjacent iff $$|x \triangle y| = 1$$

On the discrete cube, define the Simplicial ordering to be such that $$x < y$$ if:

$$|x| < |y|$$ or $$|x| = |y|$$ and $$x < y$$ in the Lexicographic order.

For a subset $$A \subset Q_n$$, define the neighbourhood to be:

$$N(A) = A \cup \{x \mid \exists y \in A, \text{ such that } x \text{ is adjacent to } y\}$$

and define the diameter of $$A$$ to be the longest path contained in $$A$$ (i.e. the maximum length over all minimal paths in $$A$$ between two vertices in $$A$$).

Harper's theorem says that if $$A \subset Q_n$$ and $$C \subset Q_n$$ is an initial segment of the Simplicial ordering of size $$|A|$$, then, then: $$|N(A)| \geq |N(C)|$$

I am asked to use Harper's Theorem to show that if a subset $$A \subset Q_n$$ has even diameter $$d < n$$, then $$|A| \leq |\{x \in Q_n \mid |x| \leq d/2\}|$$

Currently I am unsure what the relevance of Harper's Theorem is to this question.

My first thought is that for $$x,y \in Q_n$$, the minimal path length between $$x$$ and $$y$$ is $$d(x,y) = |x| + |y| - 2|x\cap y|$$

The reasoning here is that in order to go from $$x$$ to $$y$$, we must first step through $$x \cap y$$.

Now note, that $$Q_n$$ is split into levels of $$r$$-sets (i.e. sets of size $$r$$), and each level is an antichain.

If we want $$x,y$$ to be in the same level (no idea why we would), then $$|x| = |y|$$ and we get that $$d(x,y) = 2|x| - 2|x\cap y|$$. If we set this to be $$d$$, then $$|x| - |x\cap y | = \frac{d}{2}$$

This then tells us that $$\frac{d}{2} \leq |x| \leq d < n$$

This then lets us see that we can have a subset $$A \subset Q_n$$ of size $$|\{x \in Q_n \mid |x| \leq \frac{d}{2}\}|$$ (namely the set $$\{x \in Q_n \mid |x| \leq \frac{d}{2}\}$$)

Now I'm not really sure how to proceed, or how to use Harper's Theorem?

Am I even on the right track? I'm very confused about this problem and would appreciate any help, thank you!