On Graphs With a Given Endomorphism Monoid Público
Shemmer, Benjamin (2009)
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
School | |
---|---|
Department | |
Degree | |
Submission | |
Language |
|
Research Field | |
Palavra-chave | |
Committee Chair / Thesis Advisor | |
Committee Members |
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 |
|