; TeX output 2005.03.29:0921 KE&:9color push Blackhtml:color push gray 0 color pop html:G color pop3ڍ:9|&html: html:.MTvkcolor push Black color popZVg5PSfile=logo129.eps llx=0 lly=0 urx=99 ury=16 rwi=2880Bs獍+Acolor push Black color pop1!N q cmbx12CounZting
Unlab elledT=opologiesand /T=ransitivZe
Relations.s獒 jXQ ff cmr12Gunnar/Brinkmann `wApplied/MathematicsandComputerScience Ghent/University B{9000/Ghent фBelgium @0html:color push cmyk 0 1 0 0߆T ff cmtt12Gunnar.Brinkmann@ugent.be html: color pop ѭBrendan/D.McKaycolor push rgb 0 .5 0html:=K`y
cmr101 html: color pop 9Department/ofComputerScience $Australian/NationalUniversity 6CanbdCerra/ACT0200 rAustralia (html:color push cmyk 0 1 0 0bdm@cs.anu.edu.au html: color pop)
č vcolor push Black color pop r%"V
3
cmbx10AbstractMƍlcolor push Black color pop-̻$K`y
3
cmr10Wee܄en!umerateisomorphismclassesofseveraltypMesoftransitiverelations(equivdDa-
_len!tlye,fnitetopMologies)upto15or16poin!ts."html: html:C4'N G cmbx121(Inutro =ductionb#XQ cmr12Pfeier
[html:color push cmyk 0 1 0 03 html: color pop]presenrtedaclassicationofvXarioustypSesoforderrelationsanddeterminedtheir nrumbSers
upto12poinrts.Inthispaper,wreextendthecountsto15or16pSoints.WVedeferto[html:color push cmyk 0 1 0 03 html: color pop]forhistoricalsurvreyV,`andonlygiveenoughbackgroundtopreciselydenetheob jectswrearecounting.WVeconsideronlydirectedgraphs(digraphs)thatdonotharvemultipleedgesbutmayharveIuptooneloSopperpoinrt.V&AI(@ cmti12trffansitiverelationdigraph(TRD)ٹisIadigraphsucrhthat
color push Blackff ff -
^ٓR cmr71 html:color push gray 0 color pop html: ResearchUUsuppGortedbytheAustralianResearchCouncil. color pop :9color push Black 1G color pop *KE&:9color push Blackhtml:color push gray 0 color pop html:G color pop3ڍ&:9presencey~ofedges(+g cmmi12x;yn9)and(y;z )impliesthat(x;z )isalsopresenrt(evenifx;yn9;zaarey~not :9distinct).V(WVe; cannotusethemorenaturalterm\transitivredigraph"sinceitsmostcommon:9denitiondoSesnotallorwloops;Uthishastheunfortunateconsequencethattransitivredigraphs:9don'tcorrespSondtotransitivrerelations.)-Astrffongbcomponent+gof#adigraphisamaximalsetofpSoinrtsPsuchthatthereisadirected:9path CwithinP fromxtoy|foreacrhpairx;y.!",
cmsy102Pƹ.ٰ(ThispSermitsthezero-lengthpathfrom:9xUR2Pntoitself.)-IfXastrongcompSonenrtofaTRD!hasonlyonepoinrt,theremayormaynotbSealoop:9onthatpSoinrt.QnHowever,largerstrongcomponenrtsofaTRDhaveloSopsoneverypSointand:9edgesinbSothdirectionsbetrweeneachpairofpSoints.^IfthestrongcompSonentsofaTRD:9areBxconrtractedtosinglepSoints,XltheresultisaTRDBathathasnodirectedcyclesapartfrom:9loSops.-Twrodigraphsareisomorphic`ifthereisabijectionbSetweentheirpSoint-setsthatinduces:9abijectionbSetrweentheiredge-sets.8Thruswecanrefertoisomorphism35classes腹ofdigraphs.-OfjcourseadigraphcanbSeviewredasrepresentingsomekindoforderrelation,where:9x6y·iT~thereisanedge(x;yn9). vcInthelanguageandnotationofPfeier,wrehavethe:9follorwingcorrespSondences: :9color push Black color pop$%Ax|trffansitive?relation^correspSondsxtoanarbitraryTRD.Lett(n)bethenrumberxof$%isomorphismclassesoftransitivrerelations.8ThisisSloane'ssequenceghtml:color push cmyk 0 1 0 0A091073뀉 z ,ю, html: color pop.9:9color push Black color pop$%Aquasi-orffdercorrespSondstoaTRDsucrhthateverysingle-pSointstrongcompSonent$%hasyaloSop.RLetqn9(n)bethenrumberyofisomorphismclassesofquasi-orders.RThisis$%Sloane'ssequenceghtml:color push cmyk 0 1 0 0A001930뀉 z ,ю, html: color pop.:9color push Black color pop$%AQsoftorffderιcorrespSondsR#toaTRDwhosestrongcompSonenrtseachhaveonlyonepSoint$%(with{orwithoutloSop).GYLets(n)bethenrumber{ofisomorphismclassesofsoftorders.$%ThisisSloane'ssequenceghtml:color push cmyk 0 1 0 0A079265뀉 z ,ю, html: color pop.:9color push Black color pop$%Apffartial*orderwcorrespSondstoanTRDwhosestrongcompSonenrtsareallsinglepoinrts$%with$(loSops.`BecausewrecanremoveandreplacetheloSopsinauniquefashion,rthe$%counrtsherearethesameasforacyclicTRDs.Letp(n)bSethenumbSerofisomorphism$%classesofpartialorders. -TherekuarealsorelationshipswithnitetopSologies::ygeneraltopologiesareinbijectivre:9correspSondencebwithquasi-orders,~andT)|{Y cmr80-topologiesareinbijectivrecorrespondencewith:9partialSorders.=Thesebijectionspreservreisomorphism,sowearealsocountingisomorphism:9classesoftopSologies. -FVorenrumerativepurpSoses,wewilldenesomespSecializednumbSers.:9color push Black color pop$%qn9(n;m)isthenrumbSerofisomorphismclassesofTRDswithnpoinrtsandmstrong$%compSonenrts,suchthateachsingle-pSointstrongcompSonenthasaloSop.9:9color push Black color pop$%t(n;m)pisthenrumbSerpofisomorphismclassesofTRDswithnpoinrtsandmstrong$%compSonenrts(withsingle-poinrtstrongcomponenrtshavingaloSopornot). :9color push Black 2G color pop KE&:9color push Blackhtml:color push gray 0 color pop html:G color pop3ڍ&-IntermsofthesespSecializednrumbers,wehave"Rbeqn9(n){= ,2 cmmi8n F1u
cmex10X
ҍURm=1qn9(n;m);!t(n)9= n FX
ҍURm=1t(n;m);7wbp(n){=URqn9(n;n); Ms(n)9=URt(n;n)::9nhtml: html:d2(Computingz=g G cmmi12t&Dt