Graphs and hypercubes - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T20:30:52Z http://mathoverflow.net/feeds/question/34949 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/34949/graphs-and-hypercubes Graphs and hypercubes trying 2010-08-08T20:52:20Z 2010-08-10T06:22:52Z <p>Consider the oriented n-dimensional hypercubes <code>$C_n$</code>. </p> <ul> <li><code>$C_0$</code>: one object <code>$X_0$</code>. </li> <li><code>$C_1$</code>: <code>$X_0 \to X_1$</code>. </li> <li><code>$C_2$</code>:<br> <code>$$\begin{array}{ccc} X_{00} &amp; \rightarrow &amp; X_{01} \\ \downarrow &amp;&amp; \downarrow \\ X_{10} &amp; \rightarrow &amp; X_{11}. \end{array}$$</code></li> <li>$C_3$:<br> <code>$$\begin{array}{ccccccc} X_{000} &amp; \rightarrow &amp; \rightarrow &amp; \rightarrow &amp; X_{010} &amp;&amp; \\ \downarrow &amp; \searrow &amp; &amp; &amp; \downarrow &amp; \searrow &amp; \\ \downarrow &amp; &amp; X_{100} &amp; \rightarrow &amp; \rightarrow &amp;\rightarrow &amp; X_{110} \\ \downarrow &amp; &amp; \downarrow &amp; &amp; \downarrow &amp; &amp; \downarrow \\ X_{001} &amp; \rightarrow &amp; \downarrow &amp; \rightarrow &amp; X_{011} &amp;&amp; \downarrow \\ &amp; \searrow &amp; \downarrow &amp; &amp; &amp; \searrow &amp; \downarrow \\ &amp; &amp; X_{101} &amp; \rightarrow &amp; \rightarrow &amp; \rightarrow &amp; X_{111} \end{array}$$</code></li> </ul> <p>And so on, inductively over <code>$n \in \mathbb{N}$</code>. Some of the objects (or everyone) filling the vertices can eventually be the same. Moreover, they can be <code>$0$</code>.</p> <p>Let <code>$I$</code> be an arbitrary finite oriented diagram (graph) with no cycles (composable arrows starting and ending on one single object).</p> <p>My question is: Does always exist an <code>$n \in \mathbb{N}$</code> such that <code>$I$</code> is included in <code>$C_n$</code>? (References are also welcomed.)</p> <p>Example 1: <code>$I = \{ X \overset{f}{\underset{g}\rightrightarrows} Y \}$</code> can be arranged on <code>$C_2$</code>:<br> <code>$$\begin{array}{ccc} X &amp; \overset{f}\rightarrow &amp; Y \\ {\scriptstyle g}\downarrow &amp;&amp; \downarrow \\ Y &amp; \rightarrow &amp; 0. \end{array}$$</code></p> http://mathoverflow.net/questions/34949/graphs-and-hypercubes/34961#34961 Answer by Theo Johnson-Freyd for Graphs and hypercubes Theo Johnson-Freyd 2010-08-09T03:04:07Z 2010-08-09T03:04:07Z <p>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 <code>$X \overset{f}{\underset{g}\rightrightarrows} Y$</code> into a cube as <code>$\begin{array}{ccc} X &amp; \overset{f}\rightarrow &amp; Y \\ \downarrow &amp;&amp; \downarrow \\ X &amp; \overset{g}\rightarrow &amp; Y. \end{array}$</code>. If you would rather never have "non-zero" objects connected, that's still no problem, by bumping up dimensions sufficiently.</p> <p>You can get higher connectivity inductively as follows. Pick some vertex in your graph $I$, and stick it in as the vertex in <code>$C_0$</code>. Now pick some arrow adjacent to $I$. There are two embeddings of <code>$C_0$</code> into <code>$C_1$</code>, 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 <code>$C_1$</code>. Now pick some arrow adjacent to the graph so far. Again use that there are two embeddings of <code>$C_1$</code> into <code>$C_2$</code> 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.</p> http://mathoverflow.net/questions/34949/graphs-and-hypercubes/35009#35009 Answer by trying for Graphs and hypercubes trying 2010-08-09T14:59:24Z 2010-08-09T14:59:24Z <p>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.</p> <p>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 <code>$X \overset{f}\rightarrow Y \overset{g}\rightarrow Z$</code> into the diagram<br> <code>$\begin{array} X &amp; \overset{f}\rightarrow &amp; Y \\ \downarrow &amp;&amp; \downarrow \\ Y &amp; \overset{g}\rightarrow &amp; Z \end{array}$</code> where the vertical arrows are 0. This square is commutative, but where is the composition <code>$g \circ f$</code>? Even if you consider the identity from Y on the top to Y on the bottom, the diagram wouldn't be commutative.</p> <p>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).</p>