Primitive groups synchronize non-uniform maps of extreme ranks

João Araújo, Peter Jephson Cameron

Research output: Contribution to journalArticlepeer-review

14 Citations (Scopus)

Abstract

Let Ω be a set of cardinality n, G a permutation group on Ω,
and f : Ω

Ω a map which is not a permutation. We say that
G synchronizes f if the semigroup G, f
contains a constant
map.
The first author has conjectured that a primitive group synchronizes
any map whose kernel is non-uniform. Rystsov
proved one instance of this conjecture, namely, degree n primitive
groups synchronize maps of rank n

1 (thus, maps
with kernel type (2, 1,..., 1)). We prove some extensions of
Rystsov’s result, including this: a primitive group synchronizes
every map whose kernel type is (k, 1,..., 1). Incidentally
this result provides a new characterization of imprimitive
groups. We also prove that the conjecture above holds for
maps of extreme ranks, that is, ranks 3, 4 and n

2.
These proofs use a graph-theoretic technique due to the second
author: a transformation semigroup fails to contain a constant
map if and only if it is contained in the endomorphism
semigroup of a non-null (simple undirected) graph.
The paper finishes with a number of open problems, whose
solutions will certainly require very delicate graph theoretical
considerations.

Original languageEnglish
Pages (from-to)98-114
JournalJournal of Combinatorial Theory, Series B
Volume106
DOIs
Publication statusPublished - May 2014

Keywords

  • Synchronizing automata
  • Graph homomorphisms
  • Primitive groups
  • Černý conjecture
  • Transformation semigroups

Fingerprint

Dive into the research topics of 'Primitive groups synchronize non-uniform maps of extreme ranks'. Together they form a unique fingerprint.

Cite this