# Almost synchronizing permutation groups

This is a conjecture of João Araújo, and is related to synchronization and to the Černý conjecture in automata theory.

Let *G* be a primitive permutation group on the finite set *X*, and let *f* be a map from *X* to itself which is not a permutation. *G* is said to be *synchronizing* if, for any such map *f*, the semigroup ⟨*G,f*⟩ contains a constant function.

It is known that a synchronizing group is primitive (preserves no non-trivial equivalence relation on *X*), but the converse is false.

The group *G* is said to be *almost synchronizing* if, for any map *f* whose kernel (the partition of *X* given by inverse images of points in the image) is non-uniform (has parts of different sizes), ⟨*G,f*⟩ contains a constant function. Again, it is true that an almost synchronizing group is primitive.

Prove or disprove the converse, that is, any primitive group is almost synchronizing.

### Like this:

Like Loading...

I will talk about some progress that João and I made recently, in the Combinatorics Study Group on Friday 18 January 2013, at 4.30pm in Maths 103 at Queen Mary.