On Graphs With a Given Endomorphism Monoid Open Access

Shemmer, Benjamin (2009)

Permanent URL: https://etd.library.emory.edu/concern/etds/qz20ss72t?locale=en
Published

Abstract

Hedrlín and Pultr proved that for any monoid M there exists a graph G with endomorphism monoid isomorphic to M. We will give a construction G(M) for a graph with prescribed endomorphism monoid M. Using this construction we derive bounds on the minimum number of vertices and edges required to produce a graph with a given endomorphism monoid for various classes of finite monoids. We state bounds for the class of all monoids as well as for certain subclasses - groups, k-cancellative monoids, commutative 3-nilpotent monoids, rectangular groups, completely simple monoids, a variety of strong semillatices and others.

Table of Contents

1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1 2 Lower Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9 3 Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.1 A Reduction to P-graphs . . . . . . . . . . . . . . . . . . . . 13 3.2 Translations of Monoids . . . . . . . . . . . . . . . . . . . . .16 3.3 The graph FP. . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.4 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4 Special Classes of Monoids . . . . . . . . . . . . . . . . . . . . 26 4.1 Groups and Generalizations . . . . . . . . . . . . . . . . . . .26 4.2 Completely Simple Monoids . . . . . . . . . . . . . . . . . . .33 5 Generalizing the P-graph . . . . . . . . . . . . . . . . . . . . . 42 5.1 A general construction . . . . . . . . . . . . . . . . . . . . . 42 5.2 Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 6 Semilattice extension . . . . . . . . . . . . . . . . . . . . . . . .56 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

About this Dissertation

Rights statement
  • Permission granted by the author to include this thesis or dissertation in this repository. All rights reserved by the author. Please contact the author for information regarding the reproduction and use of this thesis or dissertation.
School
Department
Degree
Submission
Language
  • English
Research Field
Keyword
Committee Chair / Thesis Advisor
Committee Members
Last modified

Primary PDF

Thumbnail Title Date Uploaded Actions
On Graphs With a Given Endomorphism Monoid () 2018-08-28 11:32:28 -0400

Supplemental Files

Thumbnail Title Date Uploaded Actions
bibliography.tex () 2018-08-28 11:32:41 -0400
chapter4.tex () 2018-08-28 11:32:47 -0400
the-1.eps () 2018-08-28 11:32:54 -0400
preamble.tex () 2018-08-28 11:33:01 -0400
mythesis.tex () 2018-08-28 11:33:06 -0400
chapter3.tex () 2018-08-28 11:33:12 -0400
benji.eps () 2018-08-28 11:33:20 -0400
the-4.5 () 2018-08-28 11:33:27 -0400
introduction.tex () 2018-08-28 11:33:32 -0400
mydata.tex () 2018-08-28 11:33:41 -0400
the-3.4 () 2018-08-28 11:33:47 -0400
chapter6.tex () 2018-08-28 11:33:54 -0400
chapter2.tex () 2018-08-28 11:34:52 -0400
the-5.2 () 2018-08-28 11:34:58 -0400
chapter5.tex () 2018-08-28 11:35:21 -0400