INVERSE SEMIGROUPS ACTING ON GRAPHS

February27,200415:36WSPC/TrimSize:9inx6inforProceedingsLisbonProceedingsINVERSESEMIGROUPSACTINGONGRAPHSJAMESRENSHAWFacultyofMathematicalStudies,UniversityofSouthampton,Southampton,SO171BJEnglandE-mail:[e-mail]nerecentlyontheactionofsemigroupsonsetswithsomeimportantapplicationsto,forexample,thetheoryandstructureofsemigroupamalgams.Itseemsnaturaltoconsidertheactionsofsemigroupsonsets‘withstructure’andinparticularongraphsandtrees.Thetheoryofgroupactionshasprovedapowerfultoolincombinatorialgrouptheoryanditisreasonabletoexpectthatusefultechniquesinsemigrouptheorymaybeobtainedbytryingto‘port’theBass-Serretheorytoasemigroupcontext.Giventheimportanceoftransitivityinthegroupcase,webelievethatthiscanonlyreasonablybeachievedbyrestrictingourattentiontotheclassofinversesemigroups.However,itverysoonbecomesapparentthattherearesomefundamentaldifferenceswithinversesemigroupactionsandevensuchbasicnotionssuchasfreeactionshavetobetreatedcarefully.WemakeastartonthistopicinthispaperbyfirstofallrecastingsomeofSchein’sworkonrepresentationsbypartialhomomorphismsintermsofactionsandthentryingto‘mimic’someofthebasicideasfromthegrouptheorycase.Wehopetoexpandonthisinafuturepaper[5].1.IntroductionTheBass-Serretheoryofgroupactionsongraphshasprovedapowerfultoolforcombinatorialgrouptheoristsandtheaimofthispaperistoconsiderwhetherthereisany‘mileage’intryingtousethesetechniquesinthecontextofsemigrouptheoryaswell.Inparticularweaimtodevelopthetheoryof(partial)actionsofinversesemigroupsongraphsandtreesandhighlightsomeoftheconnectionswiththecaseforgroupactions.Insection2wegiveabriefaccountoftheclassicaltheoryforgroupactionsongraphsandtreesbeforeintroducingthebasicconceptofapartialinversesemigroupactioninsection3.WeincludeinthissectionabriefaccountofSchein’sω−cosetsandpartialcongruencestogetherwithabriefaccountofaconceptofafreeaction.Insection4,S−Graphsareintroducedandwe1February27,200415:36WSPC/TrimSize:9inx6inforProceedingsLisbonProceedings2presentafewexamplestoillustratetheunderlyingconcepts.Wehopetoextendthisworkinafuturepublication[5].2.TheGroupCaseWe‘setthescene’inthissectionbygivingaverybriefoutlineofthemainplayersintheBass-Serretheoryofgroups.Thenotationandterminologyismainlythatof[2]andwereferthereadertothattextformoredetails.LetGbeagroup.Bya(left)G−setwemeananon-emptyset,X,onwhichGactsbypermutations,inthesensethatthereisagrouphomomorphismρ:G→SymX,whereSymXisthesymmetricgrouponX.Asusual,wedenoteρ(g)(x)bygx.IfXandYareG−setsthenafunctionf:X→YiscalledaG−mapifforallx∈X,g∈G,f(gx)=gf(x).LetXbeaG−set.BytheG−stabilizerofanelementx∈XwemeanthesetofelementsofGthat‘fix’x,i.e.Gx={g∈G:gx=x}.ItiseasytoseethatGxisasubgroupofGandthatforanyg∈G,Ggx'gGxg−1.AgroupGissaidtoactfreelyonXifGx=1forallx∈X.TheG−orbitofanelementxisthesetGx={gx:g∈G}whichisaG−subsetofXanditiseasytoprovethatGxisG−isomorphictotheG−setofcosetsofGxinG,denotedG/Gx.ThequotientsetfortheG−setXisthesetofG−orbits,G\X={Gx:x∈X}whichclearlyhasanaturalmapX→G\X,x7→Gx.AG−transversalinXisasubsetYofXwhichcontainsexactlyoneelementofeachG−orbitofX.HencethecompositeY⊆X→G\Xisabijection.AG−graph(X,V,E,ι,τ)isanon-emptyG−setXwithdisjointnon-emptyG−subsetsVandEsuchthatX=V∪EandtwoG−mapsι,τ:E→V.IfYisaG−subsetofXthenwewriteVY=V∩Y,EY=E∩Y.IfYisnon-emptyandbothιeandτebelongtoVYforalleinYthenwesaythatYisaG−subgraphofX.Bythequotientgraph,G\X,wemeanthegraph(G\X,G\V,G\E,¯ι,¯τ)where¯ι(Ge)=Gιe,¯τ(Ge)=GτeforallGe∈G\E.IfG\Xisconnectedthenitcanbeshown(see[2])thatthereexistsubsetsY0⊆Y⊆XsuchthatYisaG−transversalinX,Y0isasubtreeofXwithVY0=VYandforeache∈EY,ι(e)∈VY.Inthiscase,YiscalledafundamentaltransversalinX.TheCayleygraphofGwithrespecttoasubsetTofGistheG−graph,X(G,T),withvertexsetV=G,edgesetE=G×Tandincidencefunctionι(g,t)=g,τ(g,t)=gtforall(g,t)∈E.February27,200415:36WSPC/TrimSize:9inx6inforProceedingsLisbonProceedings3Forexample,considerthecyclicgroupC4=hs:s4iandT={s}thentheCayleygraphcanberepresentedas◦◦◦◦//eseoos2eOOs3ewheree=(1,s)∈G×T.Thequotientgraphis OOeandacorrespondingfundamentalG−transversalis //eAgraphofgroups(G(−),Y),isaconnectedgraph(Y,V,E,ι,τ)togetherwithafunctionG(−)whichassignstoeachv∈VagroupG(v)andtoeachedgee∈EasubgroupG(e)ofG(ιe)andagroupmonomorphismte:G(e)→G(τe).Thestandardexampleisgivenasfollows.WestartwithaG−graphXsuchthatG\XisconnectedandchooseafundamentaltransversalYwithsubtreeY0.ForeachedgeeinEY,thereareuniqueverticesιe,τeinVYwhichbelongtothesameG−orbitasιe,τerespectively.FromthewaythatYisdefined,weseethatinfactιe=ιe.Byusingtheincidencefunctionsι,τ:EY→VYwecanthusmakeYintoagraph.ForeacheinEY,τeandτebelongtothesameG−orbitandsothereexiststeinGsuchthatteτe=τe-ifτe=τethenwecantakete=1.NoticethenthatGτe=teGτet−1e.Nowclearly,Ge⊆Gιe,Ge⊆GτeandsothereisanembeddingGe→Gτegivenbyg7→t−1egte.HencewehaveconstructedagraphofgroupsassociatedtoX.Forourpreviousexample,wehaveGe={1}=Gιeandtheconnectingelementte=s. OO{1}{1}February27,200415:36WSPC/TrimSize:9inx6inforProceedingsLisbonProceedings4Let(G(−),Y)beagraphofgroups.ChooseaspanningsubtreeY0ofY.ItfollowsthatVY0=VY.The