2
$\begingroup$

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!

$\endgroup$

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.