Let $G$ be a transitive permutation group acting on a set $\Omega$. A structure tree $T$ for $(G,\Omega)$ is defined as follows: if $G$ is primitive, then it consists of a root node connected by edges to each element of $\Omega$, now the set of leaves; if $G$ is not primitive, we choose a maximal block system $B_1, \dotsc, B_k$ (that is, a block system where the blocks are minimal), define a structure tree for $G$ as a group of permutations of $B_1,\dotsc,B_k$, and then draw edges from the node corresponding to each $B_i$ to the elements of $B_i$. It is clear that $G$ has a natural action on $T$.

My understanding is that the more general definition of a structure forest goes back to (Luks and Mackenzie, FOCS, 1985). Where did the concept of a structure tree first appear? (Does it really originate in the (relatively recent) study of algorithms for permutation groups, or is it older?)

  • $\begingroup$ a nitpicking comment - $\Omega$ itself is the maximal block system in your definition, no? $\endgroup$ – Dima Pasechnik Mar 15 '18 at 22:00
  • $\begingroup$ I think "maximal block system" is conventionally used to mean "maximal non-trivial block system". $\endgroup$ – H A Helfgott Mar 16 '18 at 0:46
  • $\begingroup$ there were various results proved in 1970-ies or earlier on correspondences between systems of imprimitivity, $G$-invariant functions on $\Omega$, etc, stated in terms of lattices. E.g. link.springer.com/article/10.1007%2FBF01226047 This seems to be the usual language of permutation group theorists... $\endgroup$ – Dima Pasechnik Mar 16 '18 at 1:33

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.