## 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 G, f

contains a constant

map.

The ﬁrst 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 ﬁnishes with a number of open problems, whose

solutions will certainly require very delicate graph theoretical

considerations.

Original language | English |
---|---|

Pages (from-to) | 98-114 |

Journal | Journal of Combinatorial Theory, Series B |

Volume | 106 |

DOIs | |

Publication status | Published - May 2014 |

## Keywords

- Synchronizing automata
- Graph homomorphisms
- Primitive groups
- Černý conjecture
- Transformation semigroups