Publication
Primitive groups synchronize non-uniform maps of extreme ranks
| dc.contributor.author | Araújo, João | |
| dc.contributor.author | Cameron, Peter J. | |
| dc.date.accessioned | 2015-03-25T09:35:31Z | |
| dc.date.available | 2015-03-25T09:35:31Z | |
| dc.date.issued | 2014 | |
| dc.description.abstract | 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. | por |
| dc.identifier.citation | 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 | por |
| dc.identifier.issn | 0095-8956 | |
| dc.identifier.uri | http://hdl.handle.net/10400.2/3816 | |
| dc.language.iso | eng | por |
| dc.peerreviewed | yes | por |
| dc.publisher | Elsevier | por |
| dc.relation.publisherversion | http://www.sciencedirect.com/science/article/pii/S0095895614000070 | por |
| dc.subject | Synchronizing automata | por |
| dc.subject | Graph homomorphisms | por |
| dc.subject | Primitive groups | por |
| dc.subject | Černý conjecture | por |
| dc.subject | Transformation semigroups | por |
| dc.title | Primitive groups synchronize non-uniform maps of extreme ranks | por |
| dc.type | journal article | |
| dspace.entity.type | Publication | |
| oaire.citation.endPage | 22 | por |
| oaire.citation.startPage | 1 | por |
| oaire.citation.title | Journal of Combinatorial Theory, Series B | por |
| person.familyName | Ribeiro Soares Gonçalves de Araújo | |
| person.givenName | João Jorge | |
| person.identifier.ciencia-id | EC1F-273A-9F24 | |
| person.identifier.orcid | 0000-0001-6655-2172 | |
| rcaap.rights | openAccess | por |
| rcaap.type | article | por |
| relation.isAuthorOfPublication | 1f7b349c-3251-480d-a3ac-e3cb4ef44f22 | |
| relation.isAuthorOfPublication.latestForDiscovery | 1f7b349c-3251-480d-a3ac-e3cb4ef44f22 |