# Graphs and hypercubes

Consider the oriented n-dimensional hypercubes $C_n$.

• $C_0$: one object $X_0$.
• $C_1$: $X_0 \to X_1$.
• $C_2$:
$$\begin{array}{ccc} X_{00} & \rightarrow & X_{01} \\ \downarrow && \downarrow \\ X_{10} & \rightarrow & X_{11}. \end{array}$$
• $C_3$:
$$\begin{array}{ccccccc} X_{000} & \rightarrow & \rightarrow & \rightarrow & X_{010} && \\ \downarrow & \searrow & & & \downarrow & \searrow & \\ \downarrow & & X_{100} & \rightarrow & \rightarrow &\rightarrow & X_{110} \\ \downarrow & & \downarrow & & \downarrow & & \downarrow \\ X_{001} & \rightarrow & \downarrow & \rightarrow & X_{011} && \downarrow \\ & \searrow & \downarrow & & & \searrow & \downarrow \\ & & X_{101} & \rightarrow & \rightarrow & \rightarrow & X_{111} \end{array}$$

And so on, inductively over $n \in \mathbb{N}$. Some of the objects (or everyone) filling the vertices can eventually be the same. Moreover, they can be $0$.

Let $I$ be an arbitrary finite oriented diagram (graph) with no cycles (composable arrows starting and ending on one single object).

My question is: Does always exist an $n \in \mathbb{N}$ such that $I$ is included in $C_n$? (References are also welcomed.)

Example 1: $I = \{ X \overset{f}{\underset{g}\rightrightarrows} Y \}$ can be arranged on $C_2$:
$$\begin{array}{ccc} X & \overset{f}\rightarrow & Y \\ {\scriptstyle g}\downarrow && \downarrow \\ Y & \rightarrow & 0. \end{array}$$

-
I've done my best to rewrite the post in TeX that MathOverflow can understand. Note that \begin{center} is not valid here --- only math-style commands, because this is html, not real TeX --- let alone \xymatrix. There is an effort to implement \xymatrix into MathJax (the package that we will probably eventually switch to for TeX support), but it's not there yet. –  Theo Johnson-Freyd Aug 9 '10 at 2:48
I don't understand the question. Tryinng: could you please explain the words "included" and "arranged on" in the last three lines of your post. –  André Henriques Aug 10 '10 at 16:29
Dear André, "inclusion" means a functor from a diagram 'I' to an hypercube $C_n$. –  trying Aug 12 '10 at 16:15

It seems from your example that you don't mind duplicating objects: you're really asking if a graph has a "cover" that embeds in a cube. (And you must not mind this duplication if you want a positive answer, as any subgraph of a cube is bipartite.) Then depending on the rules, it seems that I can do the following. Count how many edges there are in your graph $I$, and find some cube with that many pairwise-disjoint edges (two edges are disjoint if they do not share a vertex). Then just pull apart $I$ into individual edges and label the big cube appropriately. For example, include $X \overset{f}{\underset{g}\rightrightarrows} Y$ into a cube as $\begin{array}{ccc} X & \overset{f}\rightarrow & Y \\ \downarrow && \downarrow \\ X & \overset{g}\rightarrow & Y. \end{array}$. If you would rather never have "non-zero" objects connected, that's still no problem, by bumping up dimensions sufficiently.

You can get higher connectivity inductively as follows. Pick some vertex in your graph $I$, and stick it in as the vertex in $C_0$. Now pick some arrow adjacent to $I$. There are two embeddings of $C_0$ into $C_1$, one where the vertex receives and arrow and the other where it emits one. Using the correct embedding, you can put your chosen arrow into $C_1$. Now pick some arrow adjacent to the graph so far. Again use that there are two embeddings of $C_1$ into $C_2$ to pick the one that includes your arrow. Rinse and repeat. At the end of the day, you will have constructed an "inclusion" of your graph $I$ into a cube with dimension one less than the number of objects in $I$. The image of the "inclusion" is a simply-connected graph. Note that whether $I$ had cycles was irrelevant.

-
Having a response longer than a comment, OP has posted below in response to here. –  Theo Johnson-Freyd Aug 9 '10 at 16:12

Thank you Theo for the corrections in the source text. It is my first time on MO and I am still trying to understand what it's possible to do. I do not yet understand why some latex instructions work well at a moment and not later.

About your answer : I don't think that it is exactly what I want, since I consider my hypercubes in an (additive) category C. So, if I understand well your suggestion, I should embed the diagram $X \overset{f}\rightarrow Y \overset{g}\rightarrow Z$ into the diagram
$\begin{array} X & \overset{f}\rightarrow & Y \\ \downarrow && \downarrow \\ Y & \overset{g}\rightarrow & Z \end{array}$ where the vertical arrows are 0. This square is commutative, but where is the composition $g \circ f$? Even if you consider the identity from Y on the top to Y on the bottom, the diagram wouldn't be commutative.

I hope it is clear that I think to all the diagrams, both `I' and hypercubes, as living in an additive category C, and in the embedding I want to preserve compositions and commutativity (indeed, it gives a functor which is a presheaf from I to C).

-
Dear trying: I see: you want all compositions to be preserved as well. Again, this is straightforward. Since you do not allow cycles (now I'll use that condition), you can simply enumerate all chains of arrows (there are only finitely many). Now find a big enough cube so that it can include all chains disjointly. –  Theo Johnson-Freyd Aug 9 '10 at 16:10
Oh, incidentally, it's best to leave comments to answers as comments, not as separate answers --- answers get scrambled once they have votes. In this case it would have been hard to do so, because your response is longer than a comment. Anyway, welcome to MO. –  Theo Johnson-Freyd Aug 9 '10 at 16:12
On the other hand, if your graph $I$ is not a free category, but has some commuting cells, then in general you are hosed: there is no way to put the commuting triangle into a cube by bipartiteness. –  Theo Johnson-Freyd Aug 9 '10 at 16:14
Dear Theo : Yes, there is. I said to you that I am in a category, so every pair of arrows in the hypercubes is composable. For example, you can put the diagram (sorry, I use xymatrix syntax since diagrams in latex are not working in any case, and I am not used to them) X \ar[r]^f \ar[dr]^{gf} & Y \ar[d]^g \\ & Z on the square X \ar[r]^f \ar[dr]^{gf} \ar[d]_f & Y \ar[d]^g \\ Y \ar[r]_g & Z . Dear Andre' : embedding means a functor from I to some hypercube $C_n$ (hypercubes live in an additive category C). –  trying Aug 11 '10 at 11:06