1
$\begingroup$

Given a hypercube graph $Q_n = (V,E)$, where $V = \{ 0, 1 \}^n$ (binary strings) and $E = \{ (u,v) : u=u_1 u_2 \cdots u_n, v=v_1 v_2 \cdots v_n, \exists i \text{ such that }\forall j \neq i, u_j = v_j, u_i \neq v_i\}$, i.e. there is an edge between $u$ and $v$ if and only if $u$ and $v$ differ in exactly one bit position.

Question: Sort the vertices (the binary strings) in lexicographical order, i.e. $V = \{ s_1, s_2, \ldots, s_{2^n} \}$ where $s_1 \leq s_2 \leq \cdots \leq s_{2^n}$. How to find the maximum number $M$ of edges in a "cut"? i.e.

$$ M = \max_{1 \leq k \leq 2^n-1} | \{ e =(u,v) : u \leq s_k, v\geq s_{k+1} \} |.$$

To illustrate, consider the following example for $n=3$:

enter image description here

By symmetric, we only need to consider $1 \leq k \leq 2^{n-1}$ (the left half). $M=5$ since there are $5$ edges $(u,v)$ where $u \leq s_3 = (010)$ and $v \geq s_4=(011)$. This is equivalent to draw a vertical line between $s_k$ and $s_{k+1}$, and then count the number of intersections with the edges of $Q_n$.

Is there any pattern to count the number?

$\endgroup$

1 Answer 1

3
$\begingroup$

Denote by $M_n$ the maximum number of edges over a cut of $Q_n$. I claim that $M_n = M_{n-2} + 2^{n-1}$ for all $n \geq 3$, from which you can easily find an expression for $M_n$.

Let $E_n^i$ be the subset of edges in $Q_n$ that connect two binary words that differ in their $i$th coordinate (my coordinates go from $1$ to $n$). In your picture, $E_n^1$ consists of edges that connect each word in the left half of $Q_n$ to exactly one word in the right half. For $1 \leq k \leq 2^{n-1}$, a cut between $s_k$ and $s_{k+1}$ has exactly $k$ edges from $E_n^1$ since there are $k$ words of the left half on the left of it, and each connects to one word in the right half. If the cut doesn't disconnect the right half, its other edges come from the left half. Since the left half is symmetric, we should place the cut in its right half, i.e. the second quarter of $Q_n$ (or on one of its borders), since this maximizes the contribution of $E^1_n$.

Consider then $E^2_n$. These are the edges that connect each word of the first quarter of $Q_n$ to one word of the second quarter, and for the same reason as above, a cut placed between $s_k$ and $s_{k+1}$ for $2^{n-2} \leq k \leq 2^{n-1}$ has exactly $2^{n-1} - k$ edges from $E^2_n$. Hence it has $2^{n-1}$ edges from $E^1_n \cup E^2_n$, independently of $k$. We can then maximize the total number of edges by choosing a cut within the second quarter that maximizes its number of edges in $\bigcup_{i > 2} E^i_n$, which is $M_{n-2}$.

$\endgroup$
1
  • $\begingroup$ After running a program, I think the first few $M_n$ should be 1, 2, 5, 10, 21, 42, 85, ... and I believe this is A000975 in OEIS. $\endgroup$
    – Star Chou
    Oct 17, 2019 at 20:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .