4
$\begingroup$

We are given a $d$-dimensional hypercube $H$, where each vertex is labeled with an integer $\ell\in\{1, 2, \ldots, 2^d\}$. Let $L$ be this labelling.

Question: How many labelling permutations $L'$ of $L$ satisfy the property that each vertex $v$ of $H$ is labeled in $L'$ with one of the $d$-many labels associated in $L$ with the $d$ vertices adjacent to $v$ (i.e., lying on one of the edges of $v$) in $H$?

Example: When $d=2$, the required number of permutations is 4.

Improve this question
$\endgroup$
7
  • $\begingroup$ @MartinRubey: is that just based on some computations or is it easy to see? $\endgroup$
    – Sam Hopkins
    Commented Feb 25, 2021 at 17:37
  • 1
    $\begingroup$ Create a bipartite graph consisting of two copies of the hypercube such that the white vertices form a complete set of vertices of the hypercube, and so do the black vertices. Then a perfect matching of this graph corresponds bijectively to a permutation of the required kind. Unless I made a mistake. $\endgroup$
    – Martin Rubey
    Commented Feb 25, 2021 at 17:48
  • 1
    $\begingroup$ @MartinRubey: Ahhh, I see: another way to say it is that such a permutation is given by choosing a(n ordered) pair of perfect matchings of the hypercube. But then you linked to the wrong OEIS entry. I think you meant oeis.org/A005271. $\endgroup$
    – Sam Hopkins
    Commented Feb 25, 2021 at 17:53
  • 2
    $\begingroup$ @MartinRubey: maybe you should post your comments as an answer? There is no simple formula for the number of perfect matchings of the hypercube, but it's a well-studied quantity so I think this is the best answer that could be given. $\endgroup$
    – Sam Hopkins
    Commented Feb 25, 2021 at 17:59
  • 2
    $\begingroup$ Of course ultimately this interpretation as the square of the number of perfect matchings of the hypercube is the same as saying the number of these permutations is the permanent of the adjacency matrix of the hypercube, which is certainly true (and obvious) but not really helpful... $\endgroup$
    – Sam Hopkins
    Commented Feb 25, 2021 at 18:29

1 Answer 1

Reset to default
3
$\begingroup$

As indicated in the comments, the number in question is given by https://oeis.org/A233001, the square of the number of perfect matchings of the hypercube.

To see this, note that the hypercube $H_n$ is a bipartite graph. Let $H_n^b$ be a proper $2$-coloring of the vertices of $H_n$ with colours black and white, and let $H_n^w$ be the other (complementary) coloring. Consider now the disjoint union $U_n = H_n^b \cup H_n^w$ of these two coloured graphs.

Then a perfect matching of $U_n$ can be interpreted as a permutation of the vertices of $H_n$: the image of a vertex in $H_n$ is the partner of the corresponding black vertex in $U_n$. Conversely, a permutation $\pi$ of the vertices of $H_n$, such that $u$ and $\pi(u)$ are adjacent in $H_n$ is evidently a perfect matching of $U_n$.

Improve this answer
$\endgroup$

You must log in to answer this question.

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