Utilize este identificador para referenciar este registo: http://hdl.handle.net/10400.2/3816
Título: Primitive groups synchronize non-uniform maps of extreme ranks
Autor: Araújo, João
Cameron, Peter J.
Palavras-chave: Synchronizing automata
Graph homomorphisms
Primitive groups
Černý conjecture
Transformation semigroups
Data: 2014
Editora: Elsevier
Citação: Aráujo, João; Cameron, Peter J. - Primitive groups synchronize non-uniform maps of extreme ranks. "Journal of Combinatorial Theory" [Em linha]. ISSN 0095-8956. Vol. 106 (2014), p. 1-22
Resumo: Let Ω be a set of cardinality n, G a permutation group on Ω, and f : Ω → Ω a map which is not a permutation. We say that G synchronizes f if the semigroup hG, fi 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 − 1 (thus, maps with kernel type (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). 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 − 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.
Peer review: yes
URI: http://hdl.handle.net/10400.2/3816
ISSN: 0095-8956
Versão do Editor: http://www.sciencedirect.com/science/article/pii/S0095895614000070
Aparece nas colecções:Matemática e Estatística - Artigos em revistas internacionais / Papers in international journals

Ficheiros deste registo:
Ficheiro Descrição TamanhoFormato 
2014Primitive.pdf405,86 kBAdobe PDFVer/Abrir

FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.