Discrete Math Seminar: Wolfram Bentz

The commuting graph of a finite non-commutative semigroup S, denoted G(S), is a simple graph whose vertices are the non-central elements of S and two distinct vertices x,y are adjacent if xy=yx. This definition generalizes the corresponding concept of the commuting graph of a non-Abelian group.

Our work looks at the commuting graph of the symmetric inverse semigroup I(X). For a finite set X, let I(X) be the semigroup of all partial injective transformations on X under composition. The semigroup is universal for the class of inverse semigroups in the sense that every inverse semigroup can be embedded in I(X) for some finite set X, analog to the situation of the symmetric groups Sym(X) in group theory.

In 1989, Burns and Goldsmith classified the maximum order abelian subgroups of Sym(X). We extend this result to the semigroup I(X). As a consequence, we obtain a formula for the clique number of the commuting graph of  I(X).We also calculate the diameter of I(X) when |X| is prime or even, and obtain tight bounds on it in the remaining cases.

This is joint work with Joao Araujo (CAUL) and  Janusz Konieczny (Mary Washington).