University of Tasmania
whole_QuinnStephenJohn2002_thesis.pdf (5.09 MB)

Directed graphs and combinatorial properties of groups and semigroups

Download (5.09 MB)
posted on 2023-05-27, 15:57 authored by Quinn, SJ
This thesis is a study of several combinatorial properties of groups and semigroups. Research on combinatorial properties on groups and semigroups with all infinite subsets having certain unavoidable regularities originates from Ramsey theory and has been the subject of active investigations. In the thesis we explore several properties defined in terms of directed graphs. Chapter 1 outlines some of the earlier achievements in this area and sets the context for the thesis. The thesis continues the work by a number of well-known authors, and contains new results that give rise to interesting connections between graph, group and semigroup theoretic methods. Preliminaries and background information are included in Chapter 2 for convenience of the reader. Several technical facts used in proofs are also referenced. Chapter 3 deals with a combinatorial property related to power graphs. The power graph of a semigroup \\(S\\) is a directed graph with the set \\(S\\) of vertices, and with all edges (u, v) such that u ‚Äöv¢‚Ć v and v is the power of u. We introduce a combinatorial property defined for power graphs by analogy with several properties considered earlier. The first main theorem completely describes all pairs (\\(S\\), \\(D\\)), where \\(S\\) is a semigroup and \\(D\\) is a directed graph, and \\(S\\) satisfies this combinatorial property with respect to D. The structure of the power graphs of all finite abelian groups is then described. Chapter 4 is devoted to Cayley graphs. Let \\(T\\) be a subset of a semigroup \\(S\\). The Cayley graph Cay(\\({S, T}\\)) of \\(S\\) with respect to \\(T\\) is defined as the graph with the set \\(S\\) of vertices and with all edges (x, y), where x ‚Äöv¢‚Ć y and xt = y for some t ˜ì¬µ \\(T\\). Cayley graphs play important roles in combinatorial group and semigroup theory. For each finite directed graph \\(D\\), we obtain conditions necessary and sufficient for the Cayley graph Cay(\\({S, S})\\) of a semigroup \\(S\\) to contain a subgraph isomorphic to \\(D\\). The second main theorem of this chapter shows that every infinite semigroup \\(S\\) has an infinite subset \\(T\\) inducing a null subgraph in the Cayley graph Cay(\\({S, T}\\)). A natural question that arises is when the Cayley graph of a semigroup belongs to one of the classes well known in graph theory. The next theorems in this chapter characterise all finite inverse semigroups and all commutative inverse semigroups with bipartite Cayley graphs. We then obtain necessary and sufficient conditions for the Cayley graph of a semigroup to comprise the disjoint union of complete graphs. This result is used to describe all monoids \\(S\\) and subsets \\(T\\) of \\(S\\) such that Cay(\\({S, T}\\)) is isomorphic to the disjoint union of complete graphs. The divisibility graph of a semigroup \\(S\\) has edges (u, v), where u belongs to the ideal generated by v. The main theorems of Chapter 5, for each directed graph \\(D\\), characterise all commutative and completely 0-simple semigroups with all infinite subsets containing divisibility subgraphs isomorphic to \\(D\\). A description is also given for all monomial matrix semigroups which possess the same property. Chapter 6 examines the concept of an annihilator set. Annihilators have been studied in combinatorial semigroup theory, in particular, in relation to unavoidable regularities in infinite sequences of elements. The annihilator graph of a semigroup \\(S\\) has edges (u, v) whenever uv = 0 and u ‚Äöv¢‚Ć v. The main theorems of this chapter describe all commutative and linear semigroups \\(S\\), where every infinite subset of \\(S\\) induces an annihilator graph that has a subgraph isomorphic to a finite directed graph \\(D\\). The author has also obtained and published new results on other related topics. A few of his theorems on automata, their languages and syntactic monoids have been included in Appendix 1.


Publication status

  • Unpublished

Rights statement

Copyright 2002 the author - The University is continuing to endeavour to trace the copyright owner(s) and in the meantime this item has been reproduced here in good faith. We would be pleased to hear from the copyright owner(s). Thesis (PhD)--University of Tasmania, 2002. Includes bibliographical references

Repository Status

  • Open

Usage metrics

    Thesis collection


    No categories selected


    Ref. manager