4
$\begingroup$

In other words, how many ways are there to choose four $3$-combinations of a $6$-set, such that each two combinations contain exactly one common element, modulo dihedral group $D_6$?

For example, $\{1,2,3\}, \{1,4,5\},\{2,4,6\}, \{3,5,6\}$ and $\{2,3,4\}, \{2,5,6\},\{3,5,1\}, \{4,6,1\}$ belong to the same class, but $\{1,2,3\}, \{1,4,5\},\{2,5,6\}, \{3,4,6\}$ does not.

Context: I am considering partitions of a $4$-set and partially ordering them by refinement. The result is a lattice which I am trying to visualize by a $3$D graph. The most interesting part of the graph involves a square and a regular hexagon. For example: $\{1,2,3\}, \{1,4,5\},\{2,4,6\}, \{3,5,6\}$ leads to this visualization.

Edit: I have categorized all $30$ possibilities into $5$ orbits:

  1. (three edges of the hexagon missing, $4$ elements) $124.135.256.346, 125.134.246.356, 135.146.236.245, 136.145.235.246.$
  2. (two edges, one long diagonal missing, $6$ elements) $123.145.246.356, 124.135.236.456, 125.136.246.345, 126.135.245.346, 134.156.235.246, 135.146.234.256.$

  3. (one edge, two short diagonals missing, $12$ elements) $123.145.256.346, 123.146.245.356, 124.136.235.456, 124.136.256.345, 124.156.235.346, 125.134.236.456, 125.146.234.356, 125.146.236.345, 126.134.245.356, 126.145.235.346, 134.156.236.245, 136.145.234.256.$

  4. (two short and one long diagonal missing, $6$ elements) $123.146.256.345, 123.156.245.346, 124.156.236.345, 125.136.234.456, 126.134.235.456, 126.145.234.356.$

  5. (three long diagonals missing, $2$ elements) $123.156.246.345, 126.135.234.456.$

$\endgroup$
2
$\begingroup$

Four triangles means twelve slots to fill. There are six vertices to place in those slots. No vertex can occur three times, because it can't occur twice in a single triangle, and if there are three triangles which share that vertex and no other then there must be six other distinct vertices. In short: by two applications of the pigeonhole principle, each vertex is in precisely two of the triangles.

Therefore each vertex has four neighbours, so is missing precisely one neighbour, and they pair up: the overall graph is $K_6$ from which three non-adjacent edges have been removed.

The possibilities for the missing edges modulo the dihedral group are:

  1. Three edges of the hexagon (e.g. $0-1, 2-3, 4-5$)
  2. Two edges of the hexagon and one long diagonal (e.g. $0-1, 2-5, 3-4$)
  3. One edge of the hexagon and two short diagonals (e.g. $0-1, 2-4, 3-5$)
  4. Two short diagonals and one long diagonal (e.g. $0-2, 1-4, 3-5$)
  5. Three long diagonals (e.g. $0-3, 1-4, 2-5$)
$\endgroup$
  • $\begingroup$ Very observant. The missing edges approach also reveals the solution with the most symmetries - number $5$, so this one will be the most suited for visualization. In hindsight, this should have been obvious. These pairs represent disjunct partitions such as $\{\{1,2\},\{3\},\{4\}\}$ and $\{\{3,4\},\{1\},\{2\}\}$, whose common predecessor is a $2+2$ partition $\{\{1,2\},\{3,4\}\}$. It is only natural to place these pairs on the ends of the long diagonals. $\endgroup$ – David Tarandek Jan 9 '19 at 12:36
1
$\begingroup$

First, I'll define group equivalency such that$$\{2,3,4\},\{2,5,6\},\{3,5,1\},\{4,6,1\}\equiv\{1,3,5\},\{1,4,6\},\{2,3,4\},\{2,5,6\}$$ so that we only need to consider combinations where $1$ is in each of the first two groups.

With that restriction there are $\binom{5}{2}=10$ ways to fill the first group and $\binom{3}{2}=3$ ways to fill the second. Dividing by $2$ because each is counted twice gives $\frac{10*3}{2}=15$ ways to fill the first two groups. Each will have the form $\{a,b,c\},\{a,d,e\}$ and there are $2$ ways to fill the other two groups: $\{b,d,f\},\{c,e,f\}$ and $\{b,e,f\},\{c,d,f\}$. That gives a total of $30$ distinct combinations.

$\endgroup$
  • 1
    $\begingroup$ This is fine as far as it goes, but since OP asks "modulo dihedral group $D_6$" I think you're using too loose a group equivalency. $\endgroup$ – Peter Taylor Jan 9 '19 at 9:00
  • $\begingroup$ @PeterTaylor true. However, this answer is useful: I put these $30$ choices under the action of $D_6$ and came up with $5$ orbits. They consist of $12, 6, 6, 4, 2$ elements respectively. I will edit my question and classify them according to your $5$ possibilities. $\endgroup$ – David Tarandek Jan 9 '19 at 12:10

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.