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.


One Response to Almost synchronizing permutation groups

  1. 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.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s