3
$\begingroup$

In my math club we were discussing directed graphs on n-dimensional cubes. There are $2^n$ vertices and $n$ edges per vertex (with double-counting). An edge is either ingoing or outgoing, so there are also $2^n$ possible orientations of the edges per vertex. So it is somewhat natural to consider orientations that are bijections between the set of vertices and the set of edge-orientations.

We used a binary encoding for both sets. The vertices of the n-dim. cube are represented by $\{0,1\}^n$ (similar to a Hamming-cube) and an edge-orientation has a $1$ at the k-th place, if the edge along the k-th dimension is outgoing, 0 otherwise.

How many bijective orientations are there?

Our work was the following: There are $2^n!$ possible bijections. Not all of them are bijective orientations. There are $n2^{n-1}$ edges. Each edge puts a constraint on the bijection: If one vertex has an outgoing edge (and therefore a 1 at some k-th digit), the other must have it incoming (and therefore has a 0 at the k-th digit). So each constraint reduces the possible bijections by a half. So by our logic there should be $\frac{2^n!}{2^{n2^{n-1}}}$ bijective orientations. But we aren't sure if all the constraints are independent of each other so we came to ask for help. Thanks in advance!

By the way, if an example helps, the identity function is a bijective orientation. The vertex $0^n$ has all edges ingoing, the vertex $1^n$ has all edges outgoing and the whole orientation "flows" from $1^n$ to $0^n$.

$\endgroup$
  • $\begingroup$ I don't understand what sort of bijection you are looking for. Yes, there are $2^n$ ways to orient the edges at each vertex, but it sounds like you are looking for an edge orientation that is consistent over the whole cube. There are $n2^{n-1}$ edges, so it takes $(n-1)\log_2 n$ bits to specify one, not $n$ bits like the vertices. $\endgroup$ – Ross Millikan Jun 12 at 14:17
  • $\begingroup$ But that would give us one element of (n-1)log2(n) bits and therefore no bijection would be possible. We wanted elements of n bits on purpose, so we could have a bijection between the 2^n vertices (with a natural encoding of n bits) and the 2^n edge-orientations (also n bits). $\endgroup$ – LionCoder Jun 12 at 14:49
  • 1
    $\begingroup$ The formula can't possibly be right since it gives $\frac32$ bijective orientations when $n=2$... $\endgroup$ – Misha Lavrov Jun 12 at 15:42
  • $\begingroup$ If we only consider the $n$ edges incident on one vertex there are no constraints on the directions of the edges. There is also no parity to the vertices. We can certainly make a bijection between the edge orientations and vertices. There are $(2^n)!$ of them Is that what you were after? $\endgroup$ – Ross Millikan Jun 12 at 20:35
  • $\begingroup$ What do you mean with "no parity"? Also we're after something more specific. We want bijections that give rise to orientations. If one vertex has an outgoing edge, the vertex adjacent along that edge can't also have that edge outgoing. Bijective orientations should be consistent in this sense. $\endgroup$ – LionCoder Jun 12 at 22:45
1
$\begingroup$

Several observations / too long for a comment.

First, let me make sure I understand what you're saying. Your description is a bit confusing and it took me some time to figure out an interesting question out of it. :)

  • Let $B =\{0,1\}$, and the nodes are $v \in B^n$.

  • Let $C$ be a global configuration to orient each of the $n2^{n-1}$ edges of the hypercube. There are $2^{n2^{n-1}}$ different $C$'s.

  • Let $f_C(v) \in B^n$ describe the local edge orientations for edges of $v$, i.e. the $k$-th place of $f_C(v) = 1$ iff the edge connecting to $v$ along the $k$-th dimension is outgoing from $v$ in global configuration $C$. Note that $f_C: B^n \to B^n$.

  • You want cases where $f_C$ is bijective. In fact, you want to count $|\{C: f_C \text{ is bijective}\}|$

Am I correct? [Pls reply in comment.]


If so, then your basic counting argument is wrong on at least two levels.

First, $(2^n)!$ cannot be the numerator, because many of the $(2^n)!$ bijections $B^n \to B^n$ cannot be "implemented" as an $f_C$ for some $C$. E.g. consider a bijection $f$ which specifies that the $k$-th places of $f(u)$ and $f(v)$ both $=1$, where $u,v$ are neighboring nodes connecting along the $k$-th dimension. Clearly that edge cannot be outgoing in both directions, so this $f$ cannot be implemented as any $f_C$.

Second, $2^{n 2^{n-1}}$ also cannot be the denominator. If $f_C$ is bijective, then there is a unique all-source node $s$ where all edges are outgoing, i.e. $f(s) = 1^n$, and a unique all-sink node $t$ where all edges are incoming, i.e. $f(t) = 0^n$. However, among the set of $2^{n 2^{n-1}}$ possible $C$'s many of them will have no all-sink node, or two or more all-sink nodes, etc. This answers your question "we aren't sure if all the [edge] constraints are independent of each other" -- the answer is NO they are not independent.

In fact the one thing we can conclude with confidence is this: Every $f_C$ (bijective or not) fully specifies $C$, because all you need is to read off what happens at each node. Thus, the number of bijective $f_C$'s $ < $ the number of $C$'s $= 2^{n2^{n-1}}$.


Anyway, if my understanding is correct, I think this is actually a rather interesting question!

For $n=2$, you can in fact choose any of the $4$ nodes as all-sink and any of the remaining $3$ nodes as all-source. If they are non-neighbors, this fully specifies $C$ and the resulting $f_C$ is bijective. If they are neighbors, this leaves one edge unoriented, but there is exactly one way to orient it (in the direction from $s$ to $t$ along the $3$-hop path) s.t. the resulting $f_C$ is bijective. Thus the number of bijective $f_C$'s $= 4 \times 3 = 12$. (I am counting rotations, reflections etc as distinct.)

I am having quite a bit of trouble visualizing what happens when $n=3$ though...

$\endgroup$
  • $\begingroup$ You understood correctly. But then the thing is: we are aware that not every bijection is an orientation and that not every orientation is a bijection. But we are interested in bijective orientations and by combining two methods of counting (counting bijections and counting constraints from the orientation), we don't see why (2^n)! and 2^(n2^(n-1)) are not allowed. $\endgroup$ – LionCoder Jun 12 at 22:17
  • $\begingroup$ For a formula like $(2^n)! / R$ to be valid, you would need to argue something like: the bijections can be partitioned into classes of $R$ members each, s.t. in each class there is exactly one which is an $f_C$. This may still be true, but I don't see any easy way forward. $\endgroup$ – antkam Jun 12 at 22:23
  • $\begingroup$ Meanwhile, consider all $f: B^n \to B^n$. There is a subset $G$ which are bijections, and $|G| = (2^n)!$, and there is a different subset $H$ which are orientations (i.e. implementable by some $C$), and $|H| = 2^{n2^{n-1}}$, but what you want is the subset $G \cap H$. the only thing you can say about $|G\cap H|$ is that it is $\le |G|, |H|$, but your original argument says it is $|G|/|H|$... $\endgroup$ – antkam Jun 12 at 22:28
  • $\begingroup$ You're correct about my original argument. But why is it that the only thing one can say is that $|G \cap H| \le |G|, |H|$? I think one can be more precise. $\endgroup$ – LionCoder Jun 12 at 22:34
  • $\begingroup$ I meant: if you did not bring in further features of the problem, then in general the only thing you can say is that an intersection has size $\le$ either parent set. Of course, for this particular problem there might be much more we can say -- we just haven't found out what to say! :) $\endgroup$ – antkam Jun 12 at 22:53

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.