Dixon's theorem and random synchronization

DOI10.1016/J.DISC.2012.06.002zbMATH Open1277.05119arXiv1108.3958OpenAlexW2963569553MaRDI QIDQ385392FDOQ385392

Authors: Peter J. Cameron 

Publication date: 2 December 2013

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1108.3958

Recommendations

• On the probability of being synchronizable
• Between primitive and 2-transitive: synchronization and its friends
• A theory of transformation monoids: combinatorics and representation theory
• Primitive groups, graph endomorphisms and synchronization
• Synchronizing random almost-group automata

zbMATH Keywords

graph homomorphismssynchronizationrandom generationtransformation monoid

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Semigroups in automata theory, linguistics, etc. (20M35)

Cites Work

• On Random Generation of the Symmetric Group
• CORES OF SYMMETRIC GRAPHS
• The probability of generating the symmetric group
• The probability of generating the symmetric group
• Bounds for the probability of generating the symmetric and alternating groups.

Cited In (7)

• The existential transversal property: a generalization of homogeneity and its impact on semigroups
• Random ubiquitous transformation semigroups
• On the probability of being synchronizable
• Primitive groups, graph endomorphisms and synchronization
• Černý's conjecture and the road colouring problem
• The minimal number of generators of a finite semigroup.
• On the interplay between Černý and Babai's conjectures

Uses Software

• GAP

This page was built for publication: Dixon's theorem and random synchronization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q385392)