On the relational complexity of a finite permutation group

详细信息    查看全文

• 作者：Gregory Cherlin
• 关键词：Permutation group ; Primitive ; Affine ; Binary ; Relational complexity ; Simple group ; Orthogonal group ; Homogeneity ; Finite model theory
• 刊名：Journal of Algebraic Combinatorics
• 出版年：2016
• 出版时间：March 2016
• 年：2016
• 卷：43
• 期：2
• 页码：339-374
• 全文大小：607 KB
• 参考文献：1.Bender, H.: On groups with abelian \(2\) -subgroups. Math Z 117, 164–176 (1970)CrossRef MathSciNet MATH
  2.Cameron, P.J.: Oligomorphic Permutation Groups (London Mathematical Society Lecture Notes), vol. 152. Cambridge University Press, Cambridge (1990)
  3.Carter, R.: Simple groups of lie type. Pure and Applied Mathematics 28. Wiley, Hoboken (reprinted 1989) (1972)
  4.Cherlin, G.: Sporadic homogeneous structures. In: The Gelfand Mathematical Seminars, 1996–1999, pp.15–48. Birkhäuser (2000)
  5.Cherlin, G., Martin, G., Saracino, D.: Arities of permutation groups: wreath products and \(k\) -sets. J Comb Theory Ser A 74, 249–286 (1996)CrossRef MathSciNet MATH
  6.Conway, J., Norton, S., Parker, R., Wilson, R.: Atlas of Finite Groups: Maximal Subgroups and Characters for Simple Groups. Oxford University Press, Oxford (1985)MATH
  7.Dixon, J., Mortimer, B.: Permutation Groups, Graduate Texts in Mathematics, vol. 163. Springer, Berlin (1996)CrossRef
  8.Gagen, T.: Topics in Finite Groups (LMS Lecture Notes 16). Cambridge University Press, Cambridge (1976)
  9.Gardiner, A.: Homogeneous graphs. J Comb Theory 20, 94–102 (1976)CrossRef MathSciNet MATH
  10.Gorenstein, D.: On a theorem of Philip Hall. Pac J Math 19, 77–80 (1966)CrossRef MathSciNet MATH
  11.Gorenstein, D., Lyons, R., Solomon, R.: The Classification of the Finite Simple Groups, Number 3. Part I, Chapter A: Almost simple K-groups. Mathematical Surveys and Monographs, 40.3, pp. xvi \(+\) 419. American Mathematical Society, Providence, RI (1998)
  12.Saracino, D.: On a combinatorial problem from the model theory of wreath products I. J Comb Theory Ser A 86, 281–305 (1999)CrossRef MathSciNet MATH
  13.Saracino, D.: On a combinatorial problem from the model theory of wreath products II. J Comb Theory Ser A 86, 306–322 (1999)CrossRef MathSciNet MATH
  14.Saracino, D.: On a combinatorial problem from the model theory of wreath products III. J Comb Theory Ser A 89, 231–269 (2000)CrossRef MathSciNet MATH
  15.Sheehan, J.: Smoothly embeddable subgraphs. J Lond Math Soc 9, 212–218 (1974)CrossRef MathSciNet MATH
  16.Wilson, R.: The Finite Simple Groups. Graduate Texts in Mathematics, vol. 251. Springer, London (2009)
  17.Wiscons, J.: A reduction theorem for primitive binary permutation groups. Preprint: arXiv:​1506.​04187 (2015)
  
• 作者单位：Gregory Cherlin (1)
  
  1. Department of Mathematics, Rutgers University, Piscataway, NJ, USA
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Convex and Discrete Geometry
  Order, Lattices and Ordered Algebraic Structures
  Computer Science, general
  Group Theory and Generalizations
  
• 出版者：Springer U.S.
• ISSN：1572-9192

文摘

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). Keywords Permutation group Primitive Affine Binary Relational complexity Simple group Orthogonal group Homogeneity Finite model theory