On the existence of graphical Frobenius representations and their asymptotic enumeration. (English) Zbl 1437.05100
Summary: We give a complete answer to the GFR conjecture, proposed by J. K. Doyle et al. [J. Algebr. Comb. 48, No. 3, 405–428 (2018; Zbl 1404.05077)]: “All but finitely many Frobenius groups \(F =N\rtimes H\) with a given complement \(H\) have a GFR, with the exception when \(|H|\) is odd and \(N\) is abelian but not an elementary 2-group”. Actually, we prove something stronger, we enumerate asymptotically GFRs; we show that, besides the exceptions listed above, as \(|N|\) tends to infinity, the proportion of GFRs among all Cayley graphs over \(N\) containing \(F\) in their automorphism group tends to 1.
MSC:
| 05C25 | Graphs and abstract algebra (groups, rings, fields, etc.) |
| 05C62 | Graph representations (geometric and intersection representations, etc.) |
| 05C30 | Enumeration in graph theory |
| 20B27 | Infinite automorphism groups |
Keywords:
regular representation; Frobenius representation; Cayley graph; automorphism group; asymptotic enumerationCitations:
Zbl 1404.05077Software:
MagmaReferences:
| [1] | Babai, L., Finite digraphs with given regular automorphism groups, Period. Math. Hungar., 11, 257-270 (1980) · Zbl 0452.05030 |
| [2] | Babai, L.; Godsil, C. D., On the automorphism groups of almost all Cayley graphs, European J. Combin., 3, 9-15 (1982) · Zbl 0483.05033 |
| [3] | Babai, L.; Imrich, W., Tournaments with given regular group, Aequationes Math., 19, 232-244 (1979) · Zbl 0422.05034 |
| [4] | Bosma, W.; Cannon, J.; Playoust, C., The Magma algebra system. I. The user language, J. Symbolic Comput., 24, 3-4, 235-265 (1997) · Zbl 0898.68039 |
| [5] | Caro, Y., New Results on the Independence Number (1979), Tel-Aviv University, Tech. Report |
| [6] | Dixon, J. D.; Mortimer, B., Permutation Groups (1996), Springer-Verlag: Springer-Verlag New York · Zbl 0951.20001 |
| [7] | Dobson, E., Asymptotic automorphism groups of Cayley digraphs and graphs of abelian groups of prime-power order, Ars Math. Contemp., 3, 200-213 (2010) |
| [8] | Dobson, E.; Spiga, P.; Verret, G., Cayley graphs on abelian groups, Combinatorica, 36, 371-393 (2016) · Zbl 1399.05100 |
| [9] | Doyle, J. K., Graphical Frobenius Representations of Abstract Groups (1976), Syracuse University, Ph.D. thesis |
| [10] | Doyle, J. K.; Tucker, T. W.; Watkins, M. E., Graphical Frobenius representations, J. Algebraic Combin., 48, 405-428 (2018) · Zbl 1404.05077 |
| [11] | Godsil, C. D., GRRs for nonsolvable groups, (Algebraic Methods in Graph Theory. Algebraic Methods in Graph Theory, Szeged, 1978. Algebraic Methods in Graph Theory. Algebraic Methods in Graph Theory, Szeged, 1978, Colloq. Math. Soc. János Bolyai, vol. 25 (1981), North-Holland: North-Holland Amsterdam-New York), 221-239 · Zbl 0476.05041 |
| [12] | Guralnick, R. M.; Malle, G.; Navarro, G., Self-normalizing Sylow subgroups, Proc. Amer. Math. Soc., 132, 973-979 (2004) · Zbl 1049.20010 |
| [13] | Hegarty, P.; MacHale, D., Two-groups in which an automorphism inverts precisely half of the elements, Bull. Lond. Math. Soc., 30, 129-135 (1998) · Zbl 0934.20017 |
| [14] | Hetzel, D., Über reguläre graphische Darstellung von auflösbaren Gruppen (1976), Technische Universität: Technische Universität Berlin |
| [15] | Imrich, W., Graphen mit transitiver Automorphismengruppen, Monatsh. Math., 73, 341-347 (1969) · Zbl 0183.28503 |
| [16] | Imrich, W., Graphs with transitive abelian automorphism group, (Combinat. Theory. Combinat. Theory, Proc. Colloq., Balatonfűred, 1969, Budapest (1970)), 651-656 · Zbl 0206.26202 |
| [17] | Imrich, W., On graphs with regular groups, J. Combin. Theory Ser. B, 19, 174-180 (1975) · Zbl 0282.05107 |
| [18] | Li, C. H.; Zhang, H., The finite primitive groups with soluble stabilizers, and the edge-primitive s-arc transitive graphs, Proc. Lond. Math. Soc., 103, 441-472 (2011) · Zbl 1232.20005 |
| [19] | Liebeck, H.; MacHale, D., Groups with automorphisms inverting most elements, Math. Z., 124, 51-63 (1972) · Zbl 0213.30505 |
| [20] | Liebeck, M. W.; Praeger, C. E.; Saxl, J., On the O’Nan-Scott theorem for finite primitive permutation groups, J. Aust. Math. Soc. A, 44, 389-396 (1988) · Zbl 0647.20005 |
| [21] | Liebeck, M. W.; Praeger, C. E.; Saxl, J., The Maximal Factorizations of the Finite Simple Groups and Their Automorphism Groups, Memoirs of the American Mathematical Society, vol. 86, No. 432 (1990), American Mathematical Society: American Mathematical Society Providence, RI · Zbl 0703.20021 |
| [22] | Liebeck, M. W.; Praeger, C. E.; Saxl, J., On factorizations of almost simple groups, J. Algebra, 185, 409-419 (1996) · Zbl 0862.20016 |
| [23] | Miller, G. A., Groups containing the largest possible number of operators of order two, Amer. Math. Monthly, 12, 149-151 (1905) |
| [24] | Morris, J.; Spiga, P., Every finite non-solvable group admits an oriented regular representation, J. Combin. Theory Ser. B, 126, 198-234 (2017) · Zbl 1368.05161 |
| [25] | Morris, J.; Spiga, P., Classification of finite groups that admit an oriented regular representation, Bull. Lond. Math. Soc., 50, 811-831 (2018) · Zbl 1398.05105 |
| [26] | Morris, J.; Spiga, P., Asymptotic enumeration of Cayley digraphs · Zbl 1468.05118 |
| [27] | Morris, J.; Spiga, P.; Verret, G., Automorphisms of Cayley graphs on generalised dicyclic groups, European J. Combin., 43, 68-81 (2015) · Zbl 1301.05173 |
| [28] | Nowitz, L. A., Graphical regular representations of non-abelian groups. I, Canad. J. Math., 24, 993-1008 (1972) · Zbl 0249.05122 |
| [29] | Nowitz, L. A., Graphical regular representations of non-abelian groups. II, Canad. J. Math., 24, 1009-1018 (1972) · Zbl 0249.05123 |
| [30] | Pálfy, P. P., Bounds for linear groups of odd order, Proceedings of the Second International Group Theory Conference. Proceedings of the Second International Group Theory Conference, Bressanone, 1989. Proceedings of the Second International Group Theory Conference. Proceedings of the Second International Group Theory Conference, Bressanone, 1989, Rend. Circ. Mat. Palermo (2), Suppl. 23, 253-263 (1990) · Zbl 0701.20027 |
| [31] | Spiga, P., On G-locally primitive graphs of locally twisted wreath type and a conjecture of Weiss, J. Combin. Theory Ser. A, 118, 2257-2260 (2011) · Zbl 1232.05093 |
| [32] | Spiga, P., Finite groups admitting an oriented regular representation, J. Combin. Theory Ser. A, 153, 76-96 (2018) · Zbl 1369.20002 |
| [33] | Spiga, P., Cubic graphical regular representations of finite non-abelian simple groups, Comm. Algebra, 46, 2440-2450 (2018) · Zbl 1397.20005 |
| [34] | Spiga, P., On the existence of Frobenius digraphical representations, Electron. J. Combin., 25, 2, Article 2.6 pp. (2018) · Zbl 1390.05095 |
| [35] | Thompson, J., Finite groups with fixed-point-free automorphisms of prime order, Proc. Natl. Acad. Sci. USA, 45, 578-581 (1959) · Zbl 0086.25101 |
| [36] | Turán, P., An extremal problem in graph theory, Mat. Fiz. Lapok, 48, 436-452 (1941), (in Hungarian) · JFM 67.0732.03 |
| [37] | Wall, C. T.C., On groups consisting mostly of involutions, Proc. Camb. Philos. Soc., 67, 251-262 (1970) · Zbl 0197.30201 |
| [38] | Watkins, M. E., On the action of non-Abelian groups on graphs, J. Combin. Theory Ser. B, 11, 95-104 (1971) · Zbl 0227.05108 |
| [39] | Watkins, M. E.; Nowitz, L. A., On graphical regular representations of direct products of groups, Monatsh. Math., 76, 168-171 (1972) · Zbl 0242.05115 |
| [40] | Wei, V. K., A Lower Bound on the Stability Number of a Simple Graph (1981), Bell Laboratories Technical Memorandum, 81-11217-9, Murray Hill, NJ |
| [41] | Wolf, T. R., Solvable and nilpotent subgroups of \(\operatorname{GL}(n, q^m)\), Canad. J. Math., 34, 5, 1097-1111 (1982) · Zbl 0476.20028 |
| [42] | Xu, S. J.; Fang, X. G.; Wang, J.; Xu, M., On cubic s-arc transitive Cayley graphs of finite simple groups, European J. Combin., 26, 133-143 (2005) · Zbl 1060.05043 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
