1
$\begingroup$

I have an undirected graph where each node is labelled with an integer key and I'm asked to detect every simple 4-cycle, which can be seen as an empty square (i.e. the two opposite nodes of the cycle have not to be connected).

I know the labels of a generic square in the graph can be permuted in $4! = 24$ ways, but on his paper (pages 33-36) Cohen states that the symmetric group $S_4$ has $S_4 = 8$ elements, and this should allow me to focus only on $24/8 = 3$ distinct cases.

I don't understand this last point. Well, I know he probably means that the suqare has $8$ isometries (four reflections and four rotations), but I don't understand why this leads to the three cases in Figure 7 of the paper.

Thank you.

$\endgroup$
2
$\begingroup$

For each set $\{a,b,c,d\}$ of four vertices, there are three possible squares: $a-b-c-d$, $a-b-d-c$ and $a-c-b-d$. This is $|S_4|/|D_4|$, where $S_4$ is the symmetric group on four points, and $D_4$ is the dihedral group, the group of symmetries of a square.

Hear a square is a set of edges forming a square. So the squares are really $\{\{a,b\},\{b,c\},\{c,d\},\{a,d\}\}$, $\{\{a,b\},\{b,d\},\{c,d\},\{a,c\}\}$ and $\{\{a,c\},\{b,c\},\{b,d\},\{a,d\}\}$. You can check that all are distinct. Every square on $a,b,c,d$ is one of these — try finding any other one. We know that this list is exhaustive because of the computation $|S_4|/|D_4| = 3$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ OK, but why exactly those three ones? $\endgroup$ – Dree Feb 20 '14 at 14:29
  • 1
    $\begingroup$ If you consider a square as a set of edges, then there are exactly three possible squares on four vertices. You can write them in several other ways (in fact each one can be written in 8 different ways), and the exact choice is completely arbitrary. For triangles, by the way, the answer is $|S_3|/|D_3| = 6/6 = 1$: there is only one triangle on three vertices. $\endgroup$ – Yuval Filmus Feb 20 '14 at 14: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.