Asymptotically free action of permutation groups on subsets and multisets

S. Yu. Sadov

Diskretnaya Matematika, Tome 26 (2014) no. 3, pp. 101-120.

Résumé

Let $G$ be a permutation group acting on a finite set $\Omega$ of cardinality $n$. The number of orbits of the induced action of $G$ on the set $\Omega_m$ of all $m$-element subsets of $\Omega$ obeys the trivial estimates $|\Omega_m|/|G|\leq |\Omega_m/G|\leq |\Omega_m|$. In this paper the upper estimate is improved in terms of the minimal degree of the group $G$ or the minimal degree of its subset with small complement. In particular, using the universal estimates obtained by Bochert for the minimal degree of a group and by Babai–Pyber for the order of a group, in terms of $n$ only we demonstrate that if $G$ is a 2-transitive group other than the full symmetric or the alternating groups, $m$ and $n$ are large enough, and the ratio $m/n$ is bounded away from $0$ and $1$, then $|\Omega_m/G|\approx |\Omega_m|/|G|$. Similar results hold true for the induced action of $G$ on the set $\Omega_{(m)}$ of all $m$-element multisets with elements drawn from $\Omega$, provided that the ratio $m/(m+n)$ is uniformly bounded away from $0$ and $1$.

Détail

Keywords: permutation group, regular orbits, average size of the stabilizer, minimal degree of a group, asymptotics of the number of orbits, enumeration of affine configurations, enumeration of graphs, asymptotically free action.

Bibliographie

[1] Kharari F., Palmer E., Perechislenie grafov, Mir, Moskva, 1977 | MR

[2] Ford G. W., Uhlenbeck G. E., “Combinatorial problems in the theory of graphs. IV”, Proc. Nat. Acad. Sci. USA, 43 (1957), 163–167 | DOI | MR

[3] Wright E. M., “Graphs on unlabelled nodes with a given number of edges”, Acta Math., 126 (1971), 1–9 | DOI | MR | Zbl

[4] Hoffman F., Welch L., “Totally variant sets in finite groups and vector spaces”, Canad. J. Math., 20 (1968), 701–710 | MR | Zbl

[5] Strazdins I., “Universal affine classification of Boolean functions”, Acta Applic. Math., 46 (1997), 147–167 | DOI | MR | Zbl

[6] Wild M., “The asymptotic number of inequivalent binary codes and nonisomorphic binary matroids”, Finite Fields and Their Appl., 6 (2000), 192–202 | DOI | MR | Zbl

[7] Wild M., “The asymptotic number of binary codes and binary matroids”, SIAM J. Discrete Math., 19:3 (2005), 691–699 | DOI | MR | Zbl

[8] Xiang-Dong Hou, “On the asymptotic number of non-equivalent binary linear codes”, Finite Fields and Their Appl., 13 (2007), 318–326 | DOI | MR | Zbl

[9] Xiang-Dong Hou, “On the asymptotic number of inequivalent binary self-dual codes”, J. Comb. Theory Ser. A, 114 (2007), 522–544 | DOI | MR | Zbl

[10] Xiang-Dong Hou, “Asymptotic numbers of non-equivalent codes in three notions of equivalence”, Linear and Multilinear Algebra, 57:2 (2009), 111–122 | DOI | MR | Zbl

[11] Lax R. F., “On the character of $S_n$ acting on subspaces of $\mathbb F_n$”, Finite Fields and Their Appl., 10 (2004), 315–322 | DOI | MR | Zbl

[12] Cameron P. J., “Permutation groups on unordered sets”, Higher Combinatorics, Proc. NATO Adv. Study Inst. Series, 31, ed. M. Aigner, D. Reidel Publ. Co., Amsterdam, 1978, 217–239 | MR

[13] Cameron P. J., Permutation groups, Cambridge Univ. Press, Cambridge, 1999 | MR | Zbl

[14] Siemons J., “Permutation groups on unordered sets. I”, Arch. Math., 43 (1984), 483–487 | DOI | MR | Zbl

[15] Livingstone D., Wagner A., “Transitivity of finite permutation groups on unordered sets”, Math. Zeitschr., 90 (1965), 393–403 | DOI | MR | Zbl

[16] Kochetov M., Parsons N., Sadov S., “Counting fine gradings on matrix algebras and on classical simple Lie algebras”, Int. J. of Algebra and Computations, 23:7 (2013), 1755–1781 | DOI | MR | Zbl

[17] Wielandt H., Finite permutation groups, Academic Press, New York–London, 1964 | MR | Zbl

[18] Duchet P., “Hypergraphs”, Handbook of Combinatorics, eds. Graham R., Grötschel M., Lovász L., Elsevier Science, Amsterdam–Lausanne–New York–Oxford–Shannon–Tokyo, 1995, 381–432 | MR | Zbl

[19] Korshunov A. D., “O moschnosti nekotorykh klassov grafov”, Doklady AN SSSR, 193:6 (1970), 1230–1233 | Zbl

[20] Dixon J. D., Mortimer B., Permutation groups, Springer-Verlag, New York, 1996 | MR | Zbl

[21] Erdős P., Lehner J., “The distribution of the number of summands in the partitions of a positive integer”, Duke Math. J., 8:2 (1941), 335–345 | DOI | MR | Zbl

[22] Babai L., “On the order of uniprimitive permutation groups”, Ann. Math., 113:3 (1981), 553–568 | DOI | MR | Zbl

[23] Zemlyachenko V. N., Korneenko N. M., Tyshkevich R. I., “Problema izomorfizma grafov”, Teoriya slozhnosti vychislenii. I, Zap. nauchn. sem. LOMI, 118, 1982, 83–158 | MR | Zbl

[24] Lovász L., Pyber L., Welsh D. J. A., Ziegler G. M., “Combinatorics in Pure Mathematics”, Handbook of Combinatorics, eds. Graham R., Grötschel M., Lovász L., Elsevier Science, Amsterdam–Lausanne–New York–Oxford–Shannon–Tokyo, 1995, 2039–2082 | MR | Zbl

[25] Bochert A., “Ueber die Classe der Transitiven Substitutionengruppen. II”, Math. Ann., 49 (1897), 133–144 | DOI | MR | Zbl

[26] Herzog M., Praeger C. E., “Minimal degree of primitive permutation groups”, Combinatorial Mathematics IV (Adelaide, 1975), Lecture Notes in Math., 560, eds. Casse L. R. A., Wallis W. D., Springer-Verlag, Berlin–Heidelberg–New York, 116–122 | DOI | MR

[27] Pyber L., “On the orders of doubly transitive permutation groups, elementary estimates”, J. Comb. Theory Ser. A, 62 (1993), 361–366 | DOI | MR | Zbl

[28] Liebeck M. W., Shalev A., “Bases of primitive permutation groups”, Groups, Combinatorics and Geometry (Durham, 2001), eds. Ivanov A. A., Liebeck M. W., Saxl J., World Scientific, New Jersey–London–Singapore–Hong Kong, 2003, 147–154 | DOI | MR | Zbl

[29] Maróti A., “On the orders of primitive groups”, J. Algebra, 258:2 (2002), 631–640 | DOI | MR | Zbl

[30] Glukhov M. M., Zubov A. Yu., “O dlinakh simmetricheskikh i znakoperemennykh grupp podstanovok v razlichnykh sistemakh obrazuyuschikh (obzor)”, Mat. vopr. kibernetiki, 8, Nauka, Moskva, 2000, 3–30