zbMATH — the first resource for mathematics

The existential transversal property: a generalization of homogeneity and its impact on semigroups. (English) Zbl 07291895
Summary: Let \(G\) be a permutation group of degree \(n\), and \(k\) a positive integer with \(k\le n\). We say that \(G\) has the \(k\)-existential transversal property, or \(k\)-et, if there exists a \(k\)-subset \(A\) (of the domain \(\Omega )\) whose orbit under \(G\) contains transversals for all \(k\)-partitions \(\mathcal{P}\) of \(\Omega \). This property is a substantial weakening of the \(k\)-universal transversal property, or \(k\)-ut, investigated by the first and third author, which required this condition to hold for all \(k\)-subsets \(A\) of the domain \(\Omega \).
Our first task in this paper is to investigate the \(k\)-et property and to decide which groups satisfy it. For example, it is known that for \(k< 6\) there are several families of \(k\)-transitive groups, but for \(k\ge 6\) the only ones are alternating or symmetric groups; here we show that in the \(k\)-et context the threshold is 8, that is, for \(8\le k\le n/2\), the only transitive groups with \(k\)-et are the symmetric and alternating groups; this is best possible since the Mathieu group \(M_{24}\) (degree 24) has 7-et. We determine all groups with \(k\)-et for \(4\le k\le n/2\), up to some unresolved cases for \(k=4,5\), and describe the property for \(k=2,3\) in permutation group language. These considerations essentially answer Problem 5 proposed in the paper on \(k\)-ut referred to above; we also slightly improve the classification of groups possessing the \(k\)-ut property.
In that earlier paper, the results were applied to semigroups, in particular, to the question of when the semigroup \(\langle G,t\rangle\) is regular, where \(t\) is a map of rank \(k\) (with \(k<n/2)\); this turned out to be equivalent to the \(k\)-ut property. The question investigated here is when there is a \(k\)-subset \(A\) of the domain such that \(\langle G, t\rangle\) is regular for all maps \(t\) with image \(A\). This turns out to be much more delicate; the \(k\)-et property (with \(A\) as witnessing set) is a necessary condition, and the combination of \(k\)-et and \((k-1)\)-ut is sufficient, but the truth lies somewhere between.
Given the knowledge that a group under consideration has the necessary condition of \(k\)-et, the regularity question for \(k\le n/2\) is solved except for one sporadic group.
The paper ends with a number of problems on combinatorics, permutation groups and transformation semigroups, and their linear analogues.
20B30 Symmetric groups
20B35 Subgroups of symmetric groups
20B15 Primitive groups
20M20 Semigroups of transformations, relations, partitions, etc.
20M17 Regular semigroups
Full Text: DOI
[1] Andr\'e, Jorge; Ara\'ujo, Jo\~ao; Cameron, Peter J., The classification of partition homogeneous groups with applications to semigroup theory, J. Algebra, 452, 288-310 (2016) · Zbl 1382.20004
[2] Ara\'ujo, Jo\~ao; Bentz, Wolfram; Cameron, Peter J., Groups synchronizing a transformation of non-uniform kernel, Theoret. Comput. Sci., 498, 1-9 (2013) · Zbl 1295.68162
[3] Ara\'ujo, Jo\~ao; Bentz, Wolfram; Cameron, Peter J., Orbits of primitive \(k\)-homogenous groups on \((n-k)\)-partitions with applications to semigroups, Trans. Amer. Math. Soc., 371, 1, 105-136 (2019) · Zbl 06993228
[4] Ara\'ujo, Jo\~ao; Bentz, Wolfram; Cameron, Peter J.; Royle, Gordon; Schaefer, Artur, Primitive groups, graph endomorphisms and synchronization, Proc. Lond. Math. Soc. (3), 113, 6, 829-867 (2016) · Zbl 1360.05072
[5] Ara\'ujo, Jo\~ao; Bentz, Wolfram; Dobson, Edward; Konieczny, Janusz; Morris, Joy, Automorphism groups of circulant digraphs with applications to semigroup theory, Combinatorica, 38, 1, 1-28 (2018) · Zbl 1399.05099
[6] Ara\'ujo, Jo\~ao; Cameron, Peter J., Primitive groups synchronize non-uniform maps of extreme ranks, J. Combin. Theory Ser. B, 106, 98-114 (2014) · Zbl 1297.05162
[7] Ara\'ujo, Jo\~ao; Cameron, Peter J., Two generalizations of homogeneity in groups with applications to regular semigroups, Trans. Amer. Math. Soc., 368, 2, 1159-1188 (2016) · Zbl 1375.20003
[8] Ara\'ujo, Jo\~ao; Cameron, Peter J.; Mitchell, James D.; Neunh\"offer, Max, The classification of normalizing groups, J. Algebra, 373, 481-490 (2013) · Zbl 1277.20073
[9] Ara\'ujo, Jo\~ao; Cameron, Peter J.; Steinberg, Benjamin, Between primitive and 2-transitive: synchronization and its friends, EMS Surv. Math. Sci., 4, 2, 101-184 (2017) · Zbl 1402.68124
[10] Ara\'ujo, J.; Mitchell, J. D.; Schneider, Csaba, Groups that together with any transformation generate regular semigroups to idempotent generated semigroups, J. Algebra, 343, 93-106 (2011) · Zbl 1241.20071
[11] Arnold, Fredrick; Steinberg, Benjamin, Synchronizing groups and automata, Theoret. Comput. Sci., 359, 1-3, 101-110 (2006) · Zbl 1097.68054
[12] Baranyai, Zs., On the factorization of the complete uniform hypergraph. Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erd\Hos on his 60th birthday), Vol. I, 91-108. Colloq. Math. Soc. J\'an\=os Bolyai, Vol. 10 (1975), North-Holland, Amsterdam
[13] Bujt\'as, Csilla; Tuza, Zsolt, Smallest set-transversals of \(k\)-partitions, Graphs Combin., 25, 6, 807-816 (2009) · Zbl 1205.05114
[14] Burness, Timothy C.; Liebeck, Martin W.; Shalev, Aner, Base sizes for simple groups and a conjecture of Cameron, Proc. Lond. Math. Soc. (3), 98, 1, 116-162 (2009) · Zbl 1179.20002
[15] Cameron, Peter J., Dixon’s theorem and random synchronization, Discrete Math., 313, 11, 1233-1236 (2013) · Zbl 1277.05119
[16] Dixon, John D.; Mortimer, Brian, Permutation groups, Graduate Texts in Mathematics 163, xii+346 pp. (1996), Springer-Verlag, New York · Zbl 0951.20001
[17] GAP The GAP Group, GAP – Groups, Algorithms, and Programming, Version 4.9.1, \urlhttp://www.gap-system.org/
[18] Godsil, Chris; Royle, Gordon F., Cores of geometric graphs, Ann. Comb., 15, 2, 267-276 (2011) · Zbl 1234.05165
[19] Kantor, William M., \(4\)-homogeneous groups, Math. Z., 103, 67-68 (1968) · Zbl 0189.02303
[20] Kantor, William M., \(k\)-homogeneous groups, Math. Z., 124, 261-265 (1972) · Zbl 0232.20003
[21] Kantor, William M., On incidence matrices of finite projective and affine spaces, Math. Z., 124, 315-318 (1972) · Zbl 0228.50022
[22] Levi, I.; McAlister, D. B.; McFadden, R. B., Groups associated with finite transformation semigroups, Semigroup Forum, 61, 3, 453-467 (2000) · Zbl 0966.20031
[23] Liebeck, Martin W., The affine permutation groups of rank three, Proc. London Math. Soc. (3), 54, 3, 477-516 (1987) · Zbl 0621.20001
[24] Little, Charles H. C.; Grant, Douglas D.; Holton, D. A., On defect-\(d\) matchings in graphs, Discrete Math., 13, 1, 41-54 (1975) · Zbl 0304.05120
[25] Livingstone, Donald; Wagner, Ascher, Transitivity of finite permutation groups on unordered sets, Math. Z., 90, 393-403 (1965) · Zbl 0136.28101
[26] Neumann, Peter M., Primitive permutation groups and their section-regular partitions, Michigan Math. J., 58, 1, 309-322 (2009) · Zbl 1178.20001
[27] Radziszowski, Stanis\l aw P., Small Ramsey numbers, Electron. J. Combin., 1, Dynamic Survey 1, 30 pp. (1994)
[28] Spiga, Pablo; Verret, Gabriel, Vertex-primitive digraphs having vertices with almost equal neighbourhoods, European J. Combin., 61, 235-241 (2017) · Zbl 1352.05080
[29] Taylor, D. E., Regular \(2\)-graphs, Proc. London Math. Soc. (3), 35, 2, 257-274 (1977) · Zbl 0362.05065
[30] Taylor, Donald E., The geometry of the classical groups, Sigma Series in Pure Mathematics 9, xii+229 pp. (1992), Heldermann Verlag, Berlin · Zbl 0767.20001
[31] Watkins, Mark E., Connectivity of transitive graphs, J. Combinatorial Theory, 8, 23-29 (1970) · Zbl 0185.51702
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.