On the relational complexity of a finite permutation group

DOI10.1007/S10801-015-0636-8MaRDI QIDQ256538zbMATH OpenOpenAlexFDO

Authors Gregory Cherlin

Publication date 9 March 2016

Published in Journal of Algebraic Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10801-015-0636-8

zbMATH Keywords

affinebinaryfinite model theoryfinite permutation grouphomogeneityorthogonal groupprimitiverelational complexitysimple group

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Model-theoretic algebra (03C60) General theory for finite permutation groups (20B05) Characterization theorems for permutation groups (20B10) Primitive groups (20B15) Finite automorphism groups of algebraic, geometric, or combinatorial structures (20B25)

Review text

The relational complexity \(\rho\) of a permutation group was introduced by the author et al. [J. Comb. Theory, Ser. A 74, No. 2, 249--286 (1996; Zbl 0854.20002)]. The author determines all finite primitive affine permutation groups with relational complexity \(\phi =2\); the proof requires the classification of the finite simple groups. Moreover, he corrects the computation of \(\rho\) for alternating groups acting on \(k\)-sets, correcting a statement in [the author, in: The Gelfand Mathematical Seminars, 1996--1999. Dedicated to the memory of Chih-Han Sah. Boston, MA: Birkhäuser. 15--48 (2000; Zbl 0955.03040)].

Recommendations

• ON THE HEIGHT AND RELATIONAL COMPLEXITY OF A FINITE PERMUTATION GROUP
• Permutation groups defined by unordered relations.
• Cherlin's conjecture for finite primitive binary permutation groups
• On relational complexity and base size of finite primitive groups
• Orbit equivalence and permutation groups defined by unordered relations.

Cites work

• A reduction theorem for primitive binary permutation groups.
• Arities of permutation groups: Wreath products and \(k\)-sets
• Homogeneous graphs
• scientific article; zbMATH DE number 3906699 (Why is no real title available?)
• scientific article; zbMATH DE number 44603 (Why is no real title available?)
• scientific article; zbMATH DE number 3506951 (Why is no real title available?)
• scientific article; zbMATH DE number 1111401 (Why is no real title available?)
• scientific article; zbMATH DE number 894528 (Why is no real title available?)
• scientific article; zbMATH DE number 1421206 (Why is no real title available?)
• scientific article; zbMATH DE number 3392741 (Why is no real title available?)
• On a combinatorial problem from the model theory of wreath products. I
• On a combinatorial problem from the model theory of wreath products. II
• On a combinatorial problem from the model theory of wreath products. III
• On a theorem of Philip Hall
• On groups with abelian Sylow 2-subgroups
• Smoothly Embeddable Subgraphs
• The Finite Simple Groups

Cited in

(15)

• Cherlin's conjecture for sporadic simple groups
• Statistics for \(S_n\) acting on \(k\)-sets
• On the complexity of coloring areflexive \(h\)-ary relations with given permutation group
• A reduction theorem for primitive binary permutation groups.
• Homogenizable structures and model completeness
• ON THE HEIGHT AND RELATIONAL COMPLEXITY OF A FINITE PERMUTATION GROUP
• Cherlin's conjecture for almost simple groups of Lie rank 1
• Geometric groups of second order and related combinatorial structures
• Independence and bases: theme and variations
• The relational complexity of linear groups acting on subspaces
• The binary actions of simple groups with a single conjugacy class of involutions
• Morphism extension classes of countable L-colored graphs
• The binary actions of alternating groups
• Finite groups, fusion systems and applications. Abstracts from the workshop held March 16--21, 2025
• The binary actions of simple groups of Lie type of characteristic 2

This page was built for publication: On the relational complexity of a finite permutation group

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q256538)