2
$\begingroup$

Consider the following combinatorial problem:

Let $G$ be a finite group, and $X = \sqcup_{i\in I} X_i$ be a finite set. Suppose that for each $g\in G$ and $i\in I$ we have sets $Y_{g,i} \subset X$, which are each unions of some of the $X_i$.

Define a constrained action $\rho$ of $G$ on $X$ to be an action $\rho: G \to \operatorname{Aut}(X)$ such that $\rho(g)(x) \in Y_{g,i}$ for every $g \in G$ and $x \in X_i$.

The permutations $\prod_i S_{X_i}$ act on such constrained actions: if $\pi \in \prod_i S_{X_i}$, then with $\rho^{\pi}(g)(x) = \pi^{-1} \rho(g)(\pi x)$, we see that $\rho^{\pi}$ is again a constrained action.

Find representatives of each $\prod_i S_{X_i}$ orbit of constrained actions.

I can think of a number of approaches to this; so far they are either too dumb to work in the actual instances of this problem I care about, or too complicated for me to want to implement yet.

Does anyone know an off-the-shelf (e.g. implemented in an existing CAS) algorithm for this problem?

$\endgroup$
4
  • $\begingroup$ If for some reason it helps, I'm happy to restrict to the case that $G$ is abelian. $\endgroup$ Jun 9, 2016 at 9:26
  • $\begingroup$ As an example of a problem instance where a naive algorithm takes a few minutes (too long!) to run, consider $G=\mathbb{Z}/4\mathbb{Z} = \{0,1,2,3\}$ and $$ X = \{1\} \cup \{2, 3\} \cup \{4\} \cup \{5, 6, 7, 8\} \cup \{9, 10, 11, 12, 13, 14\} \cup \{15, 16, 17, 18\} \cup \{19, 20, 21, 22\} $$ $\endgroup$ Jun 9, 2016 at 9:26
  • $\begingroup$ \begin{align*} Y_{1,\{1\}} & = \{4\} & Y_{1,\{4\}} & = \{1\} \\ Y_{2,\{1\}} & = \{1\} & Y_{2,\{4\}} & = \{4\} \\ Y_{3,\{1\}} & = \{4\} & Y_{3,\{4\}} & = \{1\} \\ \end{align*} \begin{align*} Y_{g,\{2, 3\}} & = \{2, 3, 5, 6, 7, 8\} \\ Y_{g,\{5, 6, 7, 8\}} & = \{2, 3, 5, 6, 7, 8\} \\ Y_{g,\{9, 10, 11, 12, 13, 14\}} & = \{9, 10, 11, 12, 13, 14\} \\ Y_{g,\{15, 16, 17, 18\}} & = \{15, 16, 17, 18, 19, 20, 21, 22\} \\ Y_{g,\{19, 20, 21, 22\}} & = \{15, 16, 17, 18, 19, 20, 21, 22\} \end{align*} $\endgroup$ Jun 9, 2016 at 9:27
  • $\begingroup$ I've moved some comments to chat, and improved the clarity of the question in response to those suggestions. $\endgroup$ Jun 9, 2016 at 18:04

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.