Question

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} $$

Answer 1

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.

Answer 2

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).