Orbit equivalence and permutation groups defined by unordered relations
Francesca Dalla Volta1
and Johannes Siemons2
1Dipartimento di Matematica e Applicazioni, Università Milano Bicocca, 20125 Milano, Italy
2School of Mathematics, University of East Anglia, Norwich, NR4 7TJ UK
2School of Mathematics, University of East Anglia, Norwich, NR4 7TJ UK
DOI: 10.1007/s10801-011-0313-5
Abstract
For a set Ω an unordered relation on Ω is a family R of subsets of Ω . If R is such a relation we let G( R) \mathcal{G}(R) be the group of all permutations on Ω that preserve R, that is g belongs to G( R) \mathcal{G}(R) if and only if x\in R implies x g \in R. We are interested in permutation groups which can be represented as G= G( R) G=\mathcal{G}(R) for a suitable unordered relation R on Ω . When this is the case, we say that G is defined by the relation R, or that G is a relation group. We prove that a primitive permutation group \neq Alt( Ω ) and of degree \geq 11 is a relation group. The same is true for many classes of finite imprimitive groups, and we give general conditions on the size of blocks of imprimitivity, and the groups induced on such blocks, which guarantee that the group is defined by a relation.
Pages: 547–564
Keywords: keywords group invariant relations; regular sets; orbit closure; automorphism groups of set systems
Full Text: PDF
References
1. Albertson, M., Collins, K.: Symmetry breaking in graphs. Electron. J. Comb. 3, #R18 (1996)
2. Bates, C., Bundy, D., Hart, S., Rowley, P.: Primitive k-free permutation groups. Arch. Math. 88, 193- 198 (2007)
3. Beaumont, R., Peterson, R.: Set-transitive permutation groups. Can. J. Math. 7, 35-42 (1955)
4. Betten, D.: Geometrische Permutationsgruppen. Mitt. Math. Ges. Hamb. 10, 317-324 (1977)
5. Cameron, P.J., Neumann, P.M., Saxl, J.: On groups with no regular orbits on the set of subsets. Arch. Math. 43, 295-296 (1984)
6. Dalla Volta, F.: Regular sets for the affine and projective groups over the field of two elements. J. Geom. 33, 17-26 (1988)
7. Dalla Volta, F.: Regular sets for projective orthogonal groups over finite fields of odd characteristic. Geom. Dedic. 32, 229-245 (1989)
8. Gluck, D.: Trivial set-stabilizers in finite permutation groups. Can. J. Math. 35, 59-67 (1983)
9. Key, J.D., Siemons, J.: Regular sets and geometric groups. Results Math. 11, 97-116 (1987)
10. Key, J.D., Siemons, J.: On the k-closure of finite linear groups. Boll. Unione Mat. Ital. 7(1-B), 31-55 (1987)
11. Kisielewicz, A.: Symmetry groups of boolean functions and constructions of permutation groups. J. Algebra 199, 379-403 (1998)
12. Laflamme, C., Van Thé, N., Sauer, N.: Distinguishing number of countable homogeneous relational structures. Electron. J. Comb. 17, #R20 (2010)
13. Maróti, A.: On the orders of primitive permutation groups. J. Algebra 258, 631-640 (2002)
14. Seress, A.: Primitive groups with no regular orbits on the set of subsets. Bull. Lond. Math. Soc. 29, 697-704 (1997)
15. Seress, A., Yang, K.: On orbit equivalent, two-step imprimitive permutation groups. Contemp. Math.
2. Bates, C., Bundy, D., Hart, S., Rowley, P.: Primitive k-free permutation groups. Arch. Math. 88, 193- 198 (2007)
3. Beaumont, R., Peterson, R.: Set-transitive permutation groups. Can. J. Math. 7, 35-42 (1955)
4. Betten, D.: Geometrische Permutationsgruppen. Mitt. Math. Ges. Hamb. 10, 317-324 (1977)
5. Cameron, P.J., Neumann, P.M., Saxl, J.: On groups with no regular orbits on the set of subsets. Arch. Math. 43, 295-296 (1984)
6. Dalla Volta, F.: Regular sets for the affine and projective groups over the field of two elements. J. Geom. 33, 17-26 (1988)
7. Dalla Volta, F.: Regular sets for projective orthogonal groups over finite fields of odd characteristic. Geom. Dedic. 32, 229-245 (1989)
8. Gluck, D.: Trivial set-stabilizers in finite permutation groups. Can. J. Math. 35, 59-67 (1983)
9. Key, J.D., Siemons, J.: Regular sets and geometric groups. Results Math. 11, 97-116 (1987)
10. Key, J.D., Siemons, J.: On the k-closure of finite linear groups. Boll. Unione Mat. Ital. 7(1-B), 31-55 (1987)
11. Kisielewicz, A.: Symmetry groups of boolean functions and constructions of permutation groups. J. Algebra 199, 379-403 (1998)
12. Laflamme, C., Van Thé, N., Sauer, N.: Distinguishing number of countable homogeneous relational structures. Electron. J. Comb. 17, #R20 (2010)
13. Maróti, A.: On the orders of primitive permutation groups. J. Algebra 258, 631-640 (2002)
14. Seress, A.: Primitive groups with no regular orbits on the set of subsets. Bull. Lond. Math. Soc. 29, 697-704 (1997)
15. Seress, A., Yang, K.: On orbit equivalent, two-step imprimitive permutation groups. Contemp. Math.
© 1992–2009 Journal of Algebraic Combinatorics
©
2012 FIZ Karlsruhe /
Zentralblatt MATH for the EMIS Electronic Edition