0
$\begingroup$

In my project to construct the outer automorphism group for $S_6$ I have come across a need (or desire) to visualize a graph that has 15 vertices, with each vertex having 6 incident edges and 3 incident "triangles." (By my count, that makes 15 total vertices, 45 total edges, and 15 total triangles.) No matter how I try to draw this, I am not successful. I started with a regular 15-sided figure, but this lead nowhere quickly, and I can see clearly that if this graph even exists, it will have to be a concave/self-intersecting polygon, geometrically. Am I barking up the wrong tree, or is there a way to realize this graph?

Edit: In case anybody is wondering, the reason I am interested in this graph is because I am considering all the two-cycles in $S_6$ as "vertices," for which there are $6 \choose 2$ aka 15 total vertices; two vertices are joined by an edge if they commute, ie, if they are disjoint. Three vertices form a "triangle" if they are pairwise disjoint.

  • 2
    Label the vertices by the 15 ordered pairs of elements of the set $\{1,2,3,4,5,6\}$ and join two vertices if their corresponding ordered pairs have empty intersection.2012-10-21
  • 0
    @DerekHolt, that's exactly how I came up with the construction for the graph! But forgive me if I am being stupid, but I still don't see how that helps me draw the graph2012-10-21

1 Answers 1

2

Start with $15$ disjoint triangles, and identify the vertices in sets of $3$ (belonging to distinct triangles, but making sure that you don't identify all the vertices of one triangle with those of another) so that you end up with $15$ distinct vertices.

FWIW, here are some pictures of the graph as constructed using Derek Holt's comment. The graph is not planar, and I don't know if there is a simpler way to visualize it.

enter image description here

enter image description here

  • 0
    I was going to ask if you had a picture... and yet seeing this is strangely unsatisfying :). When you say the graph is not planar, do you mean the top and bottom pictures are not on the same plane?2012-10-21
  • 0
    Also, in the top picture, I noticed $V_(1,5)$ is connected to $V_(1,6)$ by an edge. Is this just a typo?2012-10-21
  • 0
    No, $V[1,5]$ is not connected by an edge to $V[1,6]$. What you're seeing in the top picture is the edge from $V[1,5]$ to $V[2,3]$2012-10-21
  • 0
    "Not planar" means it is impossible to draw the graph in the plane without some edges crossing.2012-10-21
  • 0
    Thank you. Just to confirm, even though it doesn't necessarily look like it, there are "only" 15 unique triangles in both pictures?2012-10-21
  • 0
    That's right. Both pictures are of the same graph, just with different arrangements of the vertices.2012-10-22
  • 1
    The 15 triangles are of the form $\{V[a,b],V[c,d],V[e,f]\}$ where $(a,b,c,d,e,f)$ is a permutation of $(1,2,3,4,5,6)$ with $a, $c, $e.2012-10-22
  • 2
    Of course you can think of the points as being associated with the 15 transpositions $(a,b)$ of $S_6$ and the 15 triangles with elements $(a,b)(c,d)(e,f)$ that are products of three disjoint transpositions. The outer automorphism of $S_6$ interchanges these two conjugacy classes in $S_6$. I don't know exactly how your project will continue, but you can see the connection now between your graph and the outer automorphism.2012-10-22
  • 0
    @DerekHolt perfect explanation. I was wondering about how $S_6$ acted on the graph, which should have been pretty obvious to me by its construction. Thank you.2012-10-23