Geodesic
On the relational complexity of a finite permutation group
Journal of Algebraic Combinatorics, Tome 43 (2016) no. 2, pp. 339-374.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

The relational complexity $\rho (X,G)$ of a finite permutation group is the least $k$ for which the group can be viewed as an automorphism group acting naturally on a homogeneous relational system whose relations are $k$-ary (an explicit permutation group theoretic version of this definition is also given). In the context of primitive permutation groups, the natural questions are (a) rough estimates, or (preferably) precise values for $\rho $ in natural cases; and (b) a rough determination of the primitive permutation groups with $\rho $ either very small (bounded) or very large (much larger than the logarithm of the degree). The rough version of (a) is relevant to (b). Our main result is an explicit characterization of the binary ($\rho =2$) primitive affine permutation groups. We also compute the precise relational complexity of $\mathrm{Alt}_n$ acting on $k$-sets, correcting (Cherlin in Sporadic homogeneous structures. In: The Gelfand Mathematical Seminars, 1996-1999, pp. 15-48, Birkhäuser 2000, Example 5).
Classification : 20B05, 20B15, 20B10, 20B25, 03C13, 03C60
Keywords: finite permutation group, primitive, affine, binary, relational complexity, simple group, orthogonal group, homogeneity, finite model theory 
@article{JAC_2016__43_2_a5,
     author = {Cherlin, Gregory},
     title = {On the relational complexity of a finite permutation group},
     journal = {Journal of Algebraic Combinatorics},
     pages = {339--374},
     publisher = {mathdoc},
     volume = {43},
     number = {2},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/JAC_2016__43_2_a5/}
}
TY  - JOUR
AU  - Cherlin, Gregory
TI  - On the relational complexity of a finite permutation group
JO  - Journal of Algebraic Combinatorics
PY  - 2016
SP  - 339
EP  - 374
VL  - 43
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/JAC_2016__43_2_a5/
LA  - en
ID  - JAC_2016__43_2_a5
ER  - 
%0 Journal Article
%A Cherlin, Gregory
%T On the relational complexity of a finite permutation group
%J Journal of Algebraic Combinatorics
%D 2016
%P 339-374
%V 43
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/JAC_2016__43_2_a5/
%G en
%F JAC_2016__43_2_a5
Cherlin, Gregory. On the relational complexity of a finite permutation group. Journal of Algebraic Combinatorics, Tome 43 (2016) no. 2, pp. 339-374. http://geodesic.mathdoc.fr/item/JAC_2016__43_2_a5/