{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "68498726",
   "metadata": {},
   "source": [
    "# Group Actions"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c46afb50",
   "metadata": {},
   "source": [
    "## Undirected graphs as orbits"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e3cb9719",
   "metadata": {},
   "source": [
    "An undirected graph G on the vertex set V={1,2,..,n}\n",
    "is a set of $E \\subseteq \\binom{V}{2}$ of edges, where each edge is a subset of V of cardinality 2.\n",
    "\n",
    "Then $S_n$ acts on V, and consequently on edges, and consequently on the set\n",
    "of graphs on V.\n",
    "\n",
    "The orbits of the latter action is isomorphism classes of graphs. \n",
    "How many non-isomorphic graphs on 4 vertices are there? List them!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "5d52b5fa",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Subsets of {1, 2, 3, 4} of size 2\n",
      "\n",
      "\n",
      "6 1\n",
      "representant: [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ], [ 3, 4 ] ]\n",
      "\n",
      "0 1\n",
      "representant: [  ]\n",
      "\n",
      "1 6\n",
      "representant: [ [ 1, 2 ] ]\n",
      "\n",
      "2 12\n",
      "representant: [ [ 1, 2 ], [ 1, 3 ] ]\n",
      "\n",
      "3 4\n",
      "representant: [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ] ]\n",
      "\n",
      "4 12\n",
      "representant: [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ] ]\n",
      "\n",
      "5 6\n",
      "representant: [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ] ]\n",
      "\n",
      "3 4\n",
      "representant: [ [ 1, 2 ], [ 1, 3 ], [ 2, 3 ] ]\n",
      "\n",
      "3 12\n",
      "representant: [ [ 1, 2 ], [ 1, 3 ], [ 2, 4 ] ]\n",
      "\n",
      "4 3\n",
      "representant: [ [ 1, 2 ], [ 1, 3 ], [ 2, 4 ], [ 3, 4 ] ]\n",
      "\n",
      "2 3\n",
      "representant: [ [ 1, 2 ], [ 3, 4 ] ]\n",
      "\n"
     ]
    }
   ],
   "source": [
    "n=4\n",
    "G = libgap.SymmetricGroup(n)\n",
    "E = Subsets([1..n],2)\n",
    "print(E)\n",
    "GR = Subsets(E)\n",
    "# print(GR)\n",
    "GRE=[sorted(list([sorted(list(f)) for f in e])) for e in sorted(GR)]\n",
    "# print(GRE)\n",
    "print()\n",
    "print()\n",
    "graphsiso=G.Orbits(GRE,libgap.OnSetsSets)\n",
    "for gr in graphsiso:\n",
    "    print(len(gr[0]),len(gr))\n",
    "    print('representant:',gr[0])\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cbfc11ca",
   "metadata": {},
   "source": [
    "Interpretation: on 4 vertices there are \n",
    "- 1 graph with 0 edges\n",
    "- 1 isoclass of graphs with 1 edges (6 isomorphic graphs) \n",
    "- 2 isoclasses of graphs wtih 2 edges, representatives {{1,2},{1,3}} and {{1,2},{3,4}}\n",
    "- 3 isoclasses of graphs with 3 edges, \n",
    "- 2 isoclasses of graphs with 4 edges\n",
    "- 1 isoclass of graphs with 5 edgeds\n",
    "- 1 isoclass of graphs with 6 edges"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d06c4e80",
   "metadata": {},
   "source": [
    "Do this analysis for n=5, n=6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8ed09c7f",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "14074131",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "dd1a082a",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "16b79223",
   "metadata": {},
   "source": [
    "We can generalise from simple graphs, where \"potential edges\" are \n",
    "- colored black (included) or\n",
    "- colored white (not included)\n",
    "\n",
    "to the case where each potential edge is given one of k colors. Permuting\n",
    "the vertices permutes these k-\"colored edges\". We set up a permutation subgroup\n",
    "of $S(N)$ with $N=\\binom{n}{2}$ and look at the cycle type of these permutations.\n",
    "Here, we list the $N$ pairs ${i,j}$ in some order, so the induced permutation on pairs \n",
    "becomes a permutation on $1..N$. This is purely for technical computer reasons. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "660be9e7",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1/24*p[1, 1, 1, 1, 1, 1] + 3/8*p[2, 2, 1, 1] + 1/3*p[3, 3] + 1/4*p[4, 2]\n",
      "1/24*x0^6 + 3/8*x0^2*x1^2 + 1/3*x2^2 + 1/4*x1*x3\n",
      "1/24*k^6 + 3/8*k^4 + 7/12*k^2\n",
      "11\n"
     ]
    }
   ],
   "source": [
    "a = lambda s,x: {s(x[0]),s(x[1])}\n",
    "n = 4\n",
    "                           \n",
    "N = binomial(n,2)\n",
    "SUBn = sorted(Subsets(n,2))\n",
    "Sn = SymmetricGroup(n)\n",
    "\n",
    "#for g in Sn:\n",
    "\n",
    "Hn = PermutationGroup(\n",
    "    [Permutation([SUBn.index(a(g,p))+1 for p in SUBn]) \n",
    "     for g in Sn])    \n",
    "   \n",
    "CycleIndexHn = Hn.cycle_index()    \n",
    "print(CycleIndexHn)    \n",
    "R=PolynomialRing(QQ,'x',N)\n",
    "\n",
    "SS= sum([(i[1]*prod([R.gens()[j-1] for j in i[0]])) for i in CycleIndexHn])\n",
    "print(SS)\n",
    "R1.<k>= PolynomialRing(QQ)\n",
    "f1 = R.hom([k for j in range(N)],R1)\n",
    "GF1 = f1(SS)\n",
    "print(GF1)\n",
    "print(GF1(2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2311a2b5",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "64c158d9",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "abd486b3",
   "metadata": {},
   "source": [
    "## Necklaces"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "faed29bd",
   "metadata": {},
   "source": [
    "Find the number of different necklaces on n beads of k colors, \n",
    "for n=2,3,4,5,6 under\n",
    "- cyclic symmetry\n",
    "- dihedral symmetry\n",
    "\n",
    "\n",
    "Also find the number of colorings using a beads of color one and b = n-a\n",
    "of color two"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "id": "b29477e5",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1/6*p[1, 1, 1, 1, 1, 1] + 1/6*p[2, 2, 2] + 1/3*p[3, 3] + 1/3*p[6]\n",
      "Multivariate Polynomial Ring in x0, x1, x2, x3, x4, x5 over Rational Field\n",
      "1/6*x0^6 + 1/6*x1^3 + 1/3*x2^2 + 1/3*x5\n",
      "1/6*k^6 + 1/6*k^3 + 1/3*k^2 + 1/3*k\n",
      "k^6 + k^5 + 3*k^4 + 4*k^3 + 3*k^2 + k + 1\n"
     ]
    }
   ],
   "source": [
    "n=6\n",
    "G = CyclicPermutationGroup(n)\n",
    "N = G.order()\n",
    "S = G.cycle_index()\n",
    "print(S)\n",
    "R=PolynomialRing(QQ,'x',n)\n",
    "print(R)\n",
    "SS= sum([(i[1]*prod([R.gens()[j-1] for j in i[0]])) for i in S])\n",
    "print(SS)\n",
    "R1.<k>= PolynomialRing(QQ)\n",
    "f1 = R.hom([k for j in range(n)],R1)\n",
    "GF1 = f1(SS)\n",
    "print(GF1)\n",
    "\n",
    "f2 = R.hom([(1 + k^(j+1)) for j in range(n)],R1)\n",
    "GF2 = f2(SS)\n",
    "print(GF2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "id": "3154a2e2",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9149c02c",
   "metadata": {},
   "source": [
    "## Acting on triangles embedded in regular n-gon\n",
    "Choose three of the vertices of a regular n-gon\n",
    "A rotation or reflection moves the points, and turns the tripple into another tripple\n",
    "Find the number of orbits under cyclic and dihedral symmetry for n=4,5,6,7,8\n",
    "Describe the orbits \n",
    "\n",
    "See https://en.wikipedia.org/wiki/Cycle_index#Example"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "id": "a2e15d82",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Subsets of {1, 2, 3, 4, 5, 6, 7, 8} of size 3\n",
      "[[6, 7, 8], [5, 7, 8], [5, 6, 8], [5, 6, 7], [4, 7, 8], [4, 6, 8], [4, 6, 7], [4, 5, 8], [4, 5, 7], [4, 5, 6], [3, 7, 8], [3, 6, 8], [3, 6, 7], [3, 5, 8], [3, 5, 7], [3, 5, 6], [3, 4, 8], [3, 4, 7], [3, 4, 6], [3, 4, 5], [2, 7, 8], [2, 6, 8], [2, 6, 7], [2, 5, 8], [2, 5, 7], [2, 5, 6], [2, 4, 8], [2, 4, 7], [2, 4, 6], [2, 4, 5], [2, 3, 8], [2, 3, 7], [2, 3, 6], [2, 3, 5], [2, 3, 4], [1, 7, 8], [1, 6, 8], [1, 6, 7], [1, 5, 8], [1, 5, 7], [1, 5, 6], [1, 4, 8], [1, 4, 7], [1, 4, 6], [1, 4, 5], [1, 3, 8], [1, 3, 7], [1, 3, 6], [1, 3, 5], [1, 3, 4], [1, 2, 8], [1, 2, 7], [1, 2, 6], [1, 2, 5], [1, 2, 4], [1, 2, 3]]\n",
      "\n",
      "\n",
      "3 8\n",
      "representant: [ 6, 7, 8 ]\n",
      "\n",
      "3 8\n",
      "representant: [ 1, 2, 4 ]\n",
      "\n",
      "3 8\n",
      "representant: [ 1, 2, 5 ]\n",
      "\n",
      "3 8\n",
      "representant: [ 1, 2, 6 ]\n",
      "\n",
      "3 8\n",
      "representant: [ 1, 2, 7 ]\n",
      "\n",
      "3 8\n",
      "representant: [ 1, 3, 5 ]\n",
      "\n",
      "3 8\n",
      "representant: [ 1, 3, 6 ]\n",
      "\n"
     ]
    }
   ],
   "source": [
    "n=6\n",
    "GS = CyclicPermutationGroup(n)\n",
    "G = GS.gap()\n",
    "E = Subsets([1..n],3)\n",
    "print(E)\n",
    "\n",
    "\n",
    "GRE=[sorted(list(e)) for e in sorted(E)]\n",
    "print(GRE)\n",
    "print()\n",
    "print()\n",
    "triangles=G.Orbits(GRE,libgap.OnSets)\n",
    "for gr in triangles:\n",
    "    print(len(gr[0]),len(gr))\n",
    "    print('representant:',gr[0])\n",
    "    print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "id": "7a637455",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Subsets of {1, 2, 3, 4, 5, 6} of size 3\n",
      "[[4, 5, 6], [3, 5, 6], [3, 4, 6], [3, 4, 5], [2, 5, 6], [2, 4, 6], [2, 4, 5], [2, 3, 6], [2, 3, 5], [2, 3, 4], [1, 5, 6], [1, 4, 6], [1, 4, 5], [1, 3, 6], [1, 3, 5], [1, 3, 4], [1, 2, 6], [1, 2, 5], [1, 2, 4], [1, 2, 3]]\n",
      "\n",
      "\n",
      "3 6\n",
      "representant: [ 4, 5, 6 ]\n",
      "\n",
      "3 12\n",
      "representant: [ 1, 2, 4 ]\n",
      "\n",
      "3 2\n",
      "representant: [ 1, 3, 5 ]\n",
      "\n"
     ]
    }
   ],
   "source": [
    "n=6\n",
    "GS = DihedralGroup(n)\n",
    "G = GS.gap()\n",
    "E = Subsets([1..n],3)\n",
    "print(E)\n",
    "\n",
    "\n",
    "GRE=[sorted(list(e)) for e in sorted(E)]\n",
    "print(GRE)\n",
    "print()\n",
    "print()\n",
    "triangles=G.Orbits(GRE,libgap.OnSets)\n",
    "for gr in triangles:\n",
    "    print(len(gr[0]),len(gr))\n",
    "    print('representant:',gr[0])\n",
    "    print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ca3b912a",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "de622bb0",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "de44bcc6",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3f9f1cdd",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f6425121",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "9135519d",
   "metadata": {},
   "source": [
    "## Colorings of the cube\n",
    "The (full) symmetry group of the cube acts faithfully  on\n",
    "- the vertex set V={1,2,3,4,5,6,7,8}, V has 8 elements\n",
    "- the edge set $E \\subset \\binom{V}{2}$ of edges of the cube; E has 12 elements\n",
    "- the face set $F \\subset \\binom{V}{4}$ of faces of the cube; F has 6 elements\n",
    "\n",
    "1. What symmetries stabilize a given vertex, a given edge, a given face?\n",
    "2. What are the fixpoints of the group elements for the given actions?\n",
    "3. Find the number of non-equivalent colorings using k colors for these 3 actions.\n",
    "4. Also find the number of black-white colorings using r black and s white colors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "d02556a2",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "48"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Action on vertices\n",
    "antipod = Permutation([(1,7),(2,8),(3,5),(4,6)])\n",
    "antipod\n",
    "rot1 = Permutation([(1,4,8,5),(2,3,7,6)])\n",
    "rot2 = Permutation([(1,2,3,4),(5,6,7,8)])\n",
    "\n",
    "G=PermutationGroup([antipod,rot1,rot2])\n",
    "G\n",
    "G.order()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "d8fe2093",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 2, 4, 7, 3, 8, 6, 5]]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "G.orbits()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "0faba4e9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "antipod.fixed_points()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "ebfc1f95",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(), (3,6)(4,5), (2,4)(6,8), (2,4,5)(3,8,6), (2,5,4)(3,6,8), (2,5)(3,8)]"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sorted(G.stabilizer(1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "096b1f7d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1/48*p[1, 1, 1, 1, 1, 1, 1, 1] + 1/8*p[2, 2, 1, 1, 1, 1] + 13/48*p[2, 2, 2, 2] + 1/6*p[3, 3, 1, 1] + 1/4*p[4, 4] + 1/6*p[6, 2]\n",
      "k^8 + k^7 + 3*k^6 + 3*k^5 + 6*k^4 + 3*k^3 + 3*k^2 + k + 1\n"
     ]
    }
   ],
   "source": [
    "n=8\n",
    "S = G.cycle_index()\n",
    "print(S)\n",
    "R=PolynomialRing(QQ,'x',n)\n",
    "#print(R)\n",
    "SS= sum([(i[1]*prod([R.gens()[j-1] for j in i[0]])) for i in S])\n",
    "#print(SS)\n",
    "R1.<k>= PolynomialRing(QQ)\n",
    "f1 = R.hom([k for j in range(n)],R1)\n",
    "GF1 = f1(SS)\n",
    "#print(GF1)\n",
    "\n",
    "f2 = R.hom([(1 + k^(j+1)) for j in range(n)],R1)\n",
    "GF2 = f2(SS)\n",
    "print(GF2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9cd0facf",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 9.5",
   "language": "sage",
   "name": "sagemath"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}