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!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.