Mathematics – Rings and Algebras
Scientific paper
2011-08-19
Mathematics
Rings and Algebras
8 pages; submitted to Discrete Mathemtics (BCC23 issue)
Scientific paper
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? This question is analogous to Dixon's Theorem that two random permutations generate the symmetric or alternating group with high probability. 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.
No associations
LandOfFree
Dixon's Theorem and random synchronization does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Dixon's Theorem and random synchronization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dixon's Theorem and random synchronization will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-108442