DiscreteMathematicsandTheoreticalComputerScience DMTCSvol. (subm.):1,bytheauthors,#rev Generation of Union Closed Sets and Moore families 7 1 0 2 Gunnar Brinkmann∗ Robin Deklerck† n a 1 UniversiteitGent,Toegepastewiskunde,informaticaenstatistiek,Krijgslaan281S9, J 2 B9000Gent,Belgium 3 1 In this article we will describe an algorithm to constructively enumerate non-isomorphic Union Closed Sets and ] O Mooresets.WeconfirmthenumberofisomorphismclassesofUnionClosedSetsandMooresetsonn≤6elements presented by other authors and give the number of isomorphism classes of Union Closed Sets and Moore sets on C 7elements. Duetotheenormousgrowthofthenumberofisomorphismclassesitseemsunlikelythatconstructive . h enumerationfor8ormoreelementswillbepossibleintheforeseeablefuture. t a m Keywords:set,generation,orderly,homomorphism,Moorefamily [ 1 Introduction v 1 5 All sets in this article are finite. A Union Closed Set is a set U of sets with the property that for all 7 A,B ∈ U we have that A∪B ∈ U. We call ΩU = SA∈UA the universe of U. Two Union Closed 3 SetswithuniverseΩU,resp. ΩU′ aredefinedtobeisomorphicifthereisabijectivemappingΩU →ΩU′ 0 inducingabijectionbetweentheUnionClosedSets. . 1 Asweareonlyinterestedinisomorphismclasses, wemayassumeΩ = Ω = {1,...,n}forsome U n 0 n. WhilethewholeuniverseΩ isbydefinitionanelementofaUnionClosedSetU,thisisnotthecase U 7 fortheemptyset. AstheemptysethasnoimpactonthestructureofaUnionClosedSet,oneofteneither 1 requirestheemptysettobeanelementofeachUnionClosedSetorforbidsittobeanelement.Wechoose : v forthefirstconvention,soourUnionClosedSetscontainΩ aswellastheemptyset. We denotea set n i X containingonerepresentativeofeachisomorphismclassofUnionClosedSetswithuniverseΩnasRn. AlthoughthefamousUnionClosedSetsconjecture(orFrankl’sconjecture)isexactlyaboutthestruc- r a tureswegeneratehere,ourapproachisnotsuitablefortestingthisconjecture. Alotisknownaboutthe structureofpossiblecounterexamplestotheUnionClosedSetsconjecture(see[BruhnandSchaudt(2015)] forasurvey),soanyapproachtoextendtheknowledgeonthesmallestsizeofapossiblecounterexample byconstructiveenumerationmustfocusonthesubsetofUnionClosedSetswiththoseadditionalstruc- turalproperties(e.g. withsmallaveragesizeofthesets,withoutsomesubconfigurationslikesingletons, etc.). ∗[email protected] †[email protected] ISSNsubm.toDMTCS(cid:13)c bytheauthorsbytheauthor(s)DistributedunderaCreativeCommonsAttribution4.0InternationalLicense 2 GunnarBrinkmann,RobinDeklerck UnionClosedSetsarecloselyrelatedtoMooreFamilies. AMoorefamilyforauniverseΩ isasetof n subsetsofΩ thatisclosedunderintersectionandcontainsΩ . ItiseasytoseethatforaUnionClosed n n SetU thesetUc ={Ω \A|A∈U}isaMoorefamily.ForaMoorefamilyMthesetMc ={Ω \A|A∈ n n M}isclosedunderunion,butastheemptysetisnotnecessarilycontainedinM, itisaUnionClosed SetforΩn\TA∈MA,whichisisomorphictoaUnionClosedSetforsomeΩn′ withn′ ≤n. AsetM ofrepresentativesofMoorefamilies(withthecanonicaldefinitionofisomorphism)forthe n universeΩn can be obtainedfrom sets R0,...,Rn of representativesof Union Closed Sets containing theemptysetas M =Sn {Uc|U ∈R } n i=0 i ifthecomplementisineachcasetakenintheuniverseΩ . n In[Higuchi(1998)],[HabibandNourine(2005)]and[Colombetal.(2010)Colomb,Irlande,andRaynaud] Moorefamiliesareenumerated.Inthemostadvancedofthesearticles–[Colombetal.(2010)Colomb,Irlande,andRaynaud] –allMoorefamiliesforn≤6werecountedandrepresentativesofisomorphismclassesweregenerated. For n = 7 the approach is not suitable for generating a set of representatives and only the number of labeledMoorefamilies–thatiswithoutconsideringisomorphisms–wasdeterminedbycleveruseofthe structureofrepresentativesofMoorefamiliesforn = 6. Inouralgorithmwedeterminethenumberof labeledUnionClosed Sets resp. labeled Moorefamiliesforn = 7 fromrepresentativesandtheirauto- morphismgroupsoftheUnionClosedSetsforn = 7,resp. n ≤ 7. Thisgivesaverygoodindependent test fortheimplemetationin [Colombetal.(2010)Colomb,Irlande,andRaynaud] aswellas forourim- plementation.WhencomputingthenumberoflabeledMoorefamiliesforΩ7fromthenumberoflabeled UnionClosedSetswithn ≤ 7,forthoseUnionClosedSetswithn < 7,thepossiblewaystochoosen verticesfrom{1,...,7}arealsotakenintoaccount. The algorithm AsubsetA⊆Ωnisrepresentedasanumberb(A)givenasthebinarynumberbn−1...b0–possiblywith leadingzeros–withb =1if(i+1)∈Aandb =0otherwise. i i WeuseanorderingofthesubsetsofΩ . ForA,B ⊆ Ω wedefineA > B if|A| < |B|(sosetswith n n moreelementsareconsideredsmallerinthisorder)or|A| = |B|andb(A) > b(B). Wheneverwerefer tolargerorsmallersets,werefertothisordering. TheconstructionalgorithmgeneratesUnionClosedSetsrecursivelybasedonthefollowingeasylemma: Lemma1. IfU 6={Ω }isaUnionClosedSetandAisthelargestnon-emptyelementinU,thenU\{A} n isalsoaUnionClosedSet. This implies that Union Closed Sets for universe Ω can be recursively constructed from the Union n ClosedSet{Ω ,∅}ofsmallestsizebysuccessivelyaddingsubsetsofΩ thatarelargerthanthelargest n n non-emptysetalreadypresent.OfcourseitisnotassuredthataddingasmallersettoaUnionClosedSet doesnotviolatetheconditionthatthesetmustbeclosedunderunions. Inordertoturnthisintoanefficientalgorithm,twoteststhatare(inprinciple)appliedtoeachstructure generatedmustbeveryfast: (i) Thetestwhetherthesetthathasbeenconstructedbyaddinganewsetisclosedunderunion. (ii) Thetestforisomorphisms. GenerationofUnionClosedSetsandMoorefamilies 3 We will first discuss (i). A straightforwardway to test (i) for a Union Closed Set U to which a new set A is addedwould be to form all unionsA∪B with B ∈ U and test whether they are in U ∪{A}. Althoughallthese steps canbe implementedasefficientbit-operations,theirnumberwouldslow down theprogram.Wedefine: Definition1. ForaUnionClosedSetU wedefinethereducedsetred(U)as red(U)={A∈U|A6=∅andthereisnoA1 6=∅inU,A1 (A} Lemma 2. Let U be a Union Closed Set for a universe Ω and let A ⊂ Ω , that is larger than any n n non-emptysetinU. ThenU ∪{A}isclosedunderunionifandonlyifA∪B ∈U forallB ∈red(U). Proof: AssumefirstthatU ∪{A}isclosedunderunionandletB ∈red(U). ThenA∪B ∈(U∪{A})andas AislargerthanB,wehaveA∪B 6=A,soA∪B ∈U. FortheotherdirectionassumethatA∪B ∈U forallB ∈red(U)andletD ∈U. ChooseanyD′ ⊂DsothatD′ ∈red(U). ThenA′ =A∪D′ ∈U andthereforealsoA′∪D ∈U asU isclosedunderunion,butA′∪D =A∪D–soA∪D ∈U ∪{A}andU ∪{A}isclosedunderunion. It wouldbe inefficientto computered(U) each time a new Union Closed Set is constructed, butas a new Union Closed Set U′ is constructedby addinga new smallest elementA to U, the set red(U′) can easilybeconstructedfromred(U)byaddingAandremovingelementsthatcontainA. Neverthelessthe few lines of code testing whether the potentialUnion Closed Set is closed under union take more than 50%ofthetotalrunningtimewhencomputingUnionClosedSetsforΩ6, whichisthelargestcasethat canbeprofiled. Inordertosolveproblem(ii)efficiently–thatisavoidthegenerationofisomorphiccopies,weusea combinationofRead/Faradzˇevtypeorderlygeneration[Faradzˇev(1976)][Read(1978)]andthehomomor- phismprinciple(seee.g. [Brinkmann(2000)]). Our first aim is to define a unique representative for each isomorphism class – called the canonical representative– andthenonlyconstructUnionClosed Sets thatare thethe canonicalrepresentativesof theirclass.WerepresentaUnionClosedSetU withk+1elementsA1 <A2 <···<Ak <∅asthestring s(U)=b(A1),...,b(Ak)ofnumbers.ForagivenisomorphismclassofUnionClosedSetsforauniverse Ω wechoosetheUnionClosedSetwiththelexicographicallysmalleststringastherepresentative. n It is in principle easy to test whether a given Union Closed Set U is the representative of its class by applying all n! possible permutations to U and comparing the strings. As n ≤ 7 this would not be extremely expensive, but due to the large number of times that this test has to be applied, still too expensivetoconstructtheUnionClosedSetsforΩ7. Inthesequelwewilldescribeawayhowthiscan beoptimized. In orderto increase the efficiencyby makingit an orderlyalgorithmof Read/Faradzˇevtype, we will usethecanonicitytestnotonlyforstructuresweoutput,butalsoduringtheconstruction: non-canonical structuresareneitheroutputnorusedintheconstruction. Thiswillonlyleadtoacorrectalgorithmifwe canprovethatcanonicalrepresentativesareconstructedfromcanonicalrepresentatives: Theorem1. LetU 6={Ω ,∅}beaUnionClosedSetfortheuniverseΩ thatisthecanonicalrepresen- n n tativeforitsisomorphismclass. IfU ={A1,A2,...,Ak,∅}withA1 <A2 <···<Ak and1≤m≤k, then{A1,A2,...,Am,∅}isalsothecanonicalrepresentativeofitsclass. 4 GunnarBrinkmann,RobinDeklerck Proof: We provetheresultform = k−1. Fork = m itistheassumptionandform < k−1itthen followsbyinduction. Lets(U)=(s1,...,sk). ForapermutationΠofΩnandaUnionClosedSetU wewriteΠ(U)forthe UnionClosed Set obtainedby replacingeach elementofa set in U by its imageunderΠ. Assume that U′ = {A1,A2,...,Ak−1,∅}isnotthecanonicalrepresentativeofitsclass. SothereisapermutationΠ of Ωn with s(Π(U′)) < s(U′). Let s(Π(U′)) = (p1,...,pk−1) and we have s(U′) = (s1,...,sk−1). Letj bethefirstpositionsothatp < s . Letusnowlookats(Π(U)) = (p′,...,p′)andletr bethe j j 1 k positionofΠ(A )inthisstring. Ifr > j thenp′ = p = s for1 ≤ i < j andp′ = p < s –sothere k i i i j j j isasmallerrepresentativefortheisomorphismclassofU. Ifr ≤ j thenp′ = p = s for1 ≤i < rand i i i p′ <p ≤s andagainwehavefoundasmallerrepresentativecontradictingtheminimalityofs(U). r r r This theorem proves that the algorithm can reject non-canonicalUnion Closed Sets and is a correct orderlyalgorithm,butthecostofthecanonicitytestwouldmakeitimpossibletodeterminethenumber ofUnionClosedSetsforΩ7. ForagivenUnionClosedSetUwithuniverseΩ and1≤m≤nwewriteU forthesubsetcontaining n m allsetsofsizek ≥mandΠ (U)forallpermutationsΠofΩ withthepropertythatΠ(U )=U . m n m m Lemma 3. LetU 6= {Ωn,∅}beanon-canonicalUnionClosedSetfortheuniverseΩn with setsA1 < A2 < ··· < Ak < ∅,sothat{A1,A2,...,Ak−1,∅}iscanonicaland|Ak| = m. Thenallpermutations Πwiths(Π(U))<s(U)areinΠm+1(U). Proof: AnypermutationΠnotinΠm+1(U)wouldbydefinitiongiveanisomorphicbutdifferentUnionClosed SetΠ(Um+1). AsduetoTheorem1s(Um+1)isminimal,s(Π(Um+1))wouldbelargerandthereforealso thepartofthestringofs(Π(U))describingsetsofsizeatleastm+1wouldimplys(Π(U))>s(U). Lemma 3 speeds up the canonicity test dramatically: We start with a list of all n! permutations as Π (U). WhentestingcanonicityofaUnionClosedSetwiththesmallestsetofsizek <n,weonlyapply n permutationsfromΠk+1(U). Duringthisapplication,wecanalreadycomputeΠk(U)bysimplyadding exactlythosepermutationstotheinitiallyemptysetΠ (U)thatfixU. Asweworkwithsmallsets, itis k noproblemtostoreandusethesetofallgroupelementsinsteadofjustasetofgenerators. Theimpactisimmediatelyclear: thenumberofpermutationsthathastobecomputedismuchsmaller andassoonassomeΠ (U)containsonlytheidentity–whichhappensveryfast–nocanonicitytestshave k to be performed,so that the total time for isomorphismcheckingis only about7% of the total running timewhencomputingUnionClosedSetsforΩ6. The implementation The algorithm was implemented in C. Next to an efficient algorithm, of course also implementation details are of crucial importance to be able to compute the results for Ω7. We precomputedthe action ofallpermutationsonallsets,sothattheycouldbeappliedveryfastanduseddatastructuresthatallow to check whether a set is contained in a Union Closed Set in constant time. Special functions were writtenthataddsetswithonlyoneelement. Asnosetsofsmallersize willbeadded,noupdatesofthe automorphismgroupsarenecessaryanditturnedoutthatatthisstageitisalsonotefficientanymoreto GenerationofUnionClosedSetsandMoorefamilies 5 n UnionClosedSet labeledUnionClosedSet 1 1 1 2 3 4 3 14 45 4 165 2.271 5 14.480 1.373.701 6 108.281.182 75.965.474.236 7 2.796.163.091.470.050 14.087.647.703.920.103.947 Tab.1: ThenumberofUnionClosedSetsandlabeledUnionClosedSets. n Moorefamilies labeledMoorefamilies 1 2 2 2 5 7 3 19 61 4 184 2480 5 14.664 1.385.552 6 108.295.846 75.973.751.474 7 2.796.163.199.765.896 14.087.648.235.707.352.472 Tab.2: ThenumberofMoorefamiliesandlabeledMoorefamilies. removesetsfromred(U)thatareasupersetofanotherelement. Detailsontheimplementationcanbest beseeninthecodewhichcanbeobtainedfromtheauthors. Results Tables1and2givethenumbersofisomorphismclassesofUnionClosedSetsandMoorefamiliesaswell asthenumbersoflabeledstructures. Upto5elementstherunningtimesarelessthan0.01seconds. For n=6itis8.2secondsonaXeon(R)CPUE5-26900runningwith2.90GHzandahighload(whichcan makeadifferencefortheseprocessors).Forn=7thejobswereruninparallelondifferentmachinesand somepartshadtobedividedfurtherinordertofinish,soitishardtogiveprecisetimes. Estimatingthe totalrunningtimefromthosepartsthatwererunonthesamemachineusedforn = 6,thetotaltimeon thistypeofmachineshouldbearound10to12CPU-years. A Union Closed Set on n elements is called sparse if the average number of elements in a set – not countingtheemptyset–isatmost n. ForUnionClosedSetsthatarenotsparse,theUnionClosedSets 2 conjectureistriviallytrue.ThefollowingtablegivesthenumberofsparseUnionClosedSets.Thesenum- berswerecomputedoncebyfilteringallUnionClosedSetsandoncebyanindependentimplementation usingspecialboundingcriteriadescribedin[Deklerck(2016)]. 6 GunnarBrinkmann,RobinDeklerck n sparseUnionClosedSet 1 0 2 0 3 0 4 2 5 27 6 3.133 7 5.777.931 Tab.3: ThenumberofsparseUnionClosedSets. Testing In[Deklerck(2016)]anindependentimplementationofthealgorithmtogetherwithspecialboundingcri- teriaforsparseUnionClosedSetswasdeveloped. Theimplementationwasusedtogenerateallisomor- phismclassesofUnionClosedSetsforΩ1,...,Ω6,and–usingspecialboundingcriteria–toconfirmthe numbersofisomorphismclassesofsparseUnionClosedSetsforΩ7. A furtherandindependentconfirmationofthe numbersforΩ1,...,Ω6 andalso an independentcon- firmationforΩ7 wasobtainedbycomputingthenumberoflabeledstructurescorrespondingtoeachrep- resentativefromthesizeoftheautomorphismgroup. Notethatasthesizeoftheautomorphismgroupis knowninthealgorithmanyway,theadditionalcostsforthistestcanbeneglected.Fromthiswecomputed thenumberof(labeled)Moorefamiliesandgotcompleteagreementwith[Colombetal.(2010)Colomb,Irlande,andRaynaud] forΩ1,...,Ω7. Duetothecompletelydifferentapproachesthismakesimplementationerrorsleadingto thesameincorrectresultsinbothcasesextremelyunlikely. Acknowledgements We wantto thankCraig Larsonforintroducingustothese interestingstructuresandforinterestingdis- cussions. FurthermorewewanttothankAnastasiiaZharkovaandMikhailAbrosimov. Thefirstversion ofthisalgorithmwasintendedasahands-onexampletoillustrateisomorphismrejectiontechniquesina coursetheyattendedat Ghentuniversity. Withouttheir visit, thisalgorithmmightnothave beendevel- oped. References References [Brinkmann(2000)] G. Brinkmann. Isomorphism rejection in structure generation programs. In P. Hansen, P. Fowler, and M. Zheng, editors, Discrete Mathematical Chemistry, volume 51 of DI- MACS Series on Discrete MathematicsandTheoreticalComputerScience, pages25–38.American MathematicalSociety,2000. [BruhnandSchaudt(2015)] H.BruhnandO.Schaudt. Thejourneyoftheunionclosedsetsconjecture. GraphsandCombinatorics,31(6):2043—-2074,2015. GenerationofUnionClosedSetsandMoorefamilies 7 [Colombetal.(2010)Colomb,Irlande,andRaynaud] P.Colomb,A.Irlande,andO. Raynaud. Counting ofMoorefamiliesforn=7. InFormalConceptAnalysis,volume5986ofLectureNotesinComputer Science,pages72–87.SpringerBerlinHeidelberg,2010. [Deklerck(2016)] R.Deklerck. Eenconstructiefalgoritmevoorunionclosedsets. Master’sthesis,Ghent university,2016. [Faradzˇev(1976)] I. Faradzˇev. Constructive enumeration of combinatorial objects. Colloques interna- tionauxC.N.R.S.No260-Proble`mesCombinatoiresetThe´oriedesGraphes,Orsay1976,pages131– 135,1976. [HabibandNourine(2005)] M.HabibandL.Nourine. ThenumberofMoorefamiliesonn=6. Discrete Mathematics,294:291–296,2005. [Higuchi(1998)] A.Higuchi. Latticesofclosureoperators. DiscreteMathematics,179:267–272,1998. [Read(1978)] R.C.Read. Everyoneawinner. AnnalsofDiscreteMathematics2,pages107–120,1978.