INEVITABLE GRAPHS: A PROOF OF THE TYPE II CONJECTURE AND SOME RELATED DECISION PROCEDURES

摘要: We verify the "Type II Conjecture" concerning question of which elements a finite monoid M are related to identity in every relational morphism with group. confirm that these form smallest submonoid, K, (containing 1 and) closed under "weak conjugation", is, if x ∈ y M, z and yzy = then yxz K zxy K. More generally, we establish similar characterization those directed graphs having edges labelled have property for such there is choice group making corresponding graph "commute". call "inevitdbleM-graph". establish, using this characterization, an effective procedure deciding from multiplication table whether "M-graph" inevitable. A significant stepping–stone towards was Tilson's 1986 construction established Type Conjecture regular elements, used here slightly modified form. But substantial credit should also be given Henckell, Margolis, Meakin Rhodes, whose recent independent work follows lines very our own.