Dixon's theorem and random synchronization

作者：Cameron Peter J^*

来源：Discrete Mathematics, 2013, 313(11): 1233-1236.

DOI：10.1016/j.disc.2012.06.002

• Transformation monoid
• Synchronization
• Graph homomorphisms
• Random generation

A transformation monoid on a set Omega is called synchronizing if it contains an element of rank 1 (that is, mapping the whole of Omega to a single point). In this paper, I tackle the question: given n and k, what is the probability that the submonoid of the full transformation monoid T-n generated by k random transformations is synchronizing?
Synchronization is motivated by automata theory, where a deterministic automaton is synchronizing if some sequence of transitions leads to the same point from any starting point. This is equivalent to requiring that the monoid generated by the transitions is synchronizing in the above sense.
The question has some similarities with a similar question about the probability that the subgroup of S-n generated by k random permutations is transitive. For k = 1, the answer is 1/n; for k = 2, Dixon's Theorem asserts that it is 1 - o(1) as n -> infinity (and good estimates are now known). For our synchronization question, for k = 1 the answer is also 1/n; I conjecture that for k = 2 iris also 1 - o(1).
Following the technique of Dixon's theorem, we need to analyse the maximal non-synchronizing submonoids of T-n. I develop a very close connection between transformation monoids and graphs, from which we obtain a description of non-synchronizing monoids as endomorphism monoids of graphs satisfying some very strong conditions. However, counting such graphs, and dealing with the intersections of their endomorphism monoids, seems difficult.

• 出版日期2013-6-6