On the diameter of semigroups of transformations and partitions

For a semigroup 𝑆 whose universal right congruence is finitely generated (or, equivalently, a semigroup satisfying the homological finiteness property of being type right-𝐹𝑃₁), the right diameter of 𝑆 is a parameter that expresses how ‘far apart’ elements of 𝑆 can be from each other, in a certain sense. To be more precise, for each finite generating set 𝑈 for the universal right congruence on 𝑆, we have a metric space (𝑆, 𝑑_𝑈 ) where 𝑑_𝑈 (𝑎, 𝑏) is the minimum length of derivations for (𝑎, 𝑏) as a con-sequence of pairs in 𝑈; the right diameter of 𝑆 with respect to 𝑈 is the diameter of this metric space. The right diameter of 𝑆 is then the minimum of the set of all right diameters with respect to finite generating sets. We develop a theoretical framework for establishing whether a semigroup of transformations or partitions on an arbitrary infinite set 𝑋 has a finitely generated universal right/left congruence, and, if it does, determining its right/left diameter. We apply this to prove results such as the following. Each of the monoids of all binary relations on 𝑋, of all partial transformations on 𝑋, and of all full transformations on 𝑋, as well as the partition and partial Brauer monoids on 𝑋, have right diameter1 and left diameter 1. The symmetric inverse monoid on 𝑋 has right diameter 2 and left diameter 2. The monoid of all injective mappings on 𝑋 has right diameter 4, and its minimal ideal (called the Baer–Levi semigroup on 𝑋)has right diameter 3, but neither of these two semigroups has a finitely generated universal left congruence. On the other hand, the semigroup of all surjective mappings on 𝑋 has left diameter 4, and its minimal ideal has left diameter 2, but neither of these semigroups has a finitely generated universal right congruence.