Primitive permutation groups and their section-regular partitions. (Q1024884)

Let \(G\leqslant\text{Sym}(X)\) and \(\rho\) be a partition of \(X\). A `section' of \(\rho\) is a subset of \(X\) containing one representative for each class of the partition. The partition \(\rho\) is called `section-regular' if there exists a section \(S\) of \(\rho\) such that \(S^g\) is also a section of \(\rho\) for all \(g\in G\). A nontrivial group \(G\leqslant\text{Sym}(X)\) is called `synchronizing' if there are no nontrivial proper section-regular partitions of \(X\). This concept has links with the theory of semigroups and automata, this is sketched in the last section of the paper. It can easily be seen that every synchronizing group is primitive. J. Araújo asked if the converse was true. The author answers by the negative and begins to investigate synchronizing groups, giving some general analysis and examples. Some results are: -- If \(G\) is transitive, every section-regular partition has all its classes of the same size. -- If \(G\) is primitive and \(\rho\) is a nontrivial proper section-regular partition of \(X\), then the number of classes and the size of classes are at least 3. -- If \(G\) is primitive but has an index 2 subgroup that is imprimitive, then \(G\) is not synchronizing. Examples of primitive non-synchronizing groups are given for several of the O'Nan-Scott types. However the number of possible degrees for such groups has density 0, and a precise big O formula for the number of possible degrees lower than a fixed \(x\) is determined. Some future possible research directions are outlined (to be undertaken by whoever wants to).