Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Can anybody help me in clearing the facts how the associativity was proved in cartesian product of 3 graphs, and thus showing isomorphism. I can easily solve for the case when its two graphs. Taking three graphs is not clear to me. Kindly help. Thanks a lot to all.

enter image description here

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

I will try to present some intuition, once you have it, it should be fairly straightforward (to prove it formally, it's enough to expand the definitions and it's done, so I guess that's not a problem here). Illustrations are at the bottom, sorry for the rainbow colors, but without them it would be even harder to digest.


It's sometimes beneficial to think about the Cartesian product of graphs in analogy to the ordinary Cartesian product. For example, product of two lines gives us a plane, product of two discrete lines results in a discrete plane. Similarly, if we arrange the vertices of the graph into a finite and discrete line, then what we will get would look like finite discrete plane (with appropriate edges). Also, as in $\mathbb{N^2}$, you can go north and south, and east and west, but you cannot use diagonals, in similar fashion you can use $\color{blue}{\text{blue}}$ edges to go east and west and you can use $\color{green}{\text{green}}$ edges to go north and south, but there are no diagonal edges.

When you add a third graph, things doesn't change much. As you can produce $\mathbb{N^3}$ as $\mathbb{N}^2 \times \mathbb{N}$ or $\mathbb{N} \times \mathbb{N}^2$, the final structure doesn't change. This is because each graph allows you to move in some "dimension", but nothing more, there are no diagonals (which might make the product non-associative). If you want to go up or down, you have to use $\color{red}{\text{red}}$ edges no matter whether the "base graph" is, $\color{blue}{\text{blue}} \times \color{green}{\text{green}}$ or just $\color{green}{\text{green}}$. Whatever order you would take the product of graphs, the only edges are $\color{blue}{\text{blue}}$ to move between $(\color{blue}{x_1},y,z)$ and $(\color{blue}{x_2},y,z)$, $\color{green}{\text{green}}$ edges to move between $(x, \color{green}{y_1},z)$ and $(x,\color{green}{y_2},z)$ and finally $\color{red}{\text{red}}$ edges to move between vertices $(x, y, \color{red}{z_1})$ and $(x,y, \color{red}{z_2})$. Moreover, whatever order you would take the product of graphs, you will get all those edges, and as such, the graphs will be isomorphic.

graph product

I hope this helps $\ddot\smile$

share|improve this answer
1  
(+1) Cool pictures! –  Tunococ Aug 2 '13 at 10:16
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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