کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4656898 | 1632987 | 2014 | 17 صفحه PDF | دانلود رایگان |
Let Ω be a set of cardinality n, G a permutation group on Ω , and f:Ω→Ωf:Ω→Ω a map which is not a permutation. We say that G synchronizes f if the semigroup 〈G,f〉〈G,f〉 contains a constant map.The first author has conjectured that a primitive group synchronizes any map whose kernel is non-uniform. Rystsov proved one instance of this conjecture, namely, degree n primitive groups synchronize maps of rank n−1n−1 (thus, maps with kernel type (2,1,…,1)(2,1,…,1)). We prove some extensions of Rystsov's result, including this: a primitive group synchronizes every map whose kernel type is (k,1,…,1)(k,1,…,1). Incidentally this result provides a new characterization of imprimitive groups. We also prove that the conjecture above holds for maps of extreme ranks, that is, ranks 3, 4 and n−2n−2.These proofs use a graph-theoretic technique due to the second author: a transformation semigroup fails to contain a constant map if and only if it is contained in the endomorphism semigroup of a non-null (simple undirected) graph.The paper finishes with a number of open problems, whose solutions will certainly require very delicate graph theoretical considerations.
Journal: Journal of Combinatorial Theory, Series B - Volume 106, May 2014, Pages 98–114