YannickFrein,BenjaminL´evˆeque,Andr´asSeb˝oLaboratoireG-SCOP,INPG,UJF,CNRS,
46,avenueFelixViallet,38031GrenobleCedex,France
November14,2007
Abstract
WeconsidertheproblemofminimizingthesizeofafamilyofsetsGsuchthateverysubsetof{1,...,n}canbewrittenasadisjointunionofatmostkmembersofG,wherekandnaregivennumbers.Thisproblemoriginatesinareal-worldapplicationaimingatthediversityofindustrialproduction.Atthesametime,theminimumof|G|sothateverysubsetof{1,...,n}istheunionoftwosetsinGhasbeenaskedbyErd˝osandstudiedrecentlybyF¨urediandKatonawithoutrequiringthedisjointnessofthesets.Asimpleconstructionprovidingafeasiblesolutionisconjecturedtobeoptimalforthisproblemforallvaluesofnandkandregardlessofthedisjointnessrequirement;weprovethisconjectureinspecialcasesincludingall(n,k)forwhichn≤3kholds,andsomeindividualvaluesofnandk.
Keywords:Tur´antypeproblems,extremalproblemsingraphsandhypergraphs,diversity,semi-finishedproducts.
1Introduction
Then-elementset{1,...,n}isdenotedby[n].Fortwopositiveintegersn,k,afamilyGofsubsetsof[n]issaidtok-generateX⊆[n]ifXisthedisjointunionofatmostkmembersofG.Itk-generatesthefamilyH⊆P([n])ifitk-generateseveryX∈H.Itiscalledan(n,k)-generatorifitgeneratestheentirepowersetP([n]),thatis,ifeverynon-emptysubsetof[n]canbe
obtainedasadisjointunionofatmostkmembersofG.Thisworkaimsatdeterminingthe(n,k)-generatorsofminimumsize.Thesizeofasetisthenumberofitselements(synonymeofcardinality).
Setsofsize1arecalledsingletons.Allthesingletons{i}(i=1,...,n)mustbecontainedinany(n,k)-generator.Wecallan(n,k)-generatorGofminimumsizeoptimal,andintroducethenotationopt(n,k):=|G|.Ageneratorcanberepresentedbyahypergraph(familyofsets)wheretheverticesaretheelementsof[n]andthehyperedgesarethemembersofG.
AsZolt´anF¨uredireports,PaulErd˝os[2]askedaboutthecasek=2allowingthetarget-setstobenotnecessarilydisjointunionsoftwomembersofG.Heconjecturedthatoptimalgeneratorsconsistofallthenon-emptysubsetsofV1andV2,whereV1,V2isapartitionof[n]intotwoalmostequalparts.Sinceeverysubsetof[n]isthedisjointunionoftwosetsinthisgenerator,itisimplicitinthisconjecturethattheoptimumvaluedoesnotdependonwhetherthetwosetsinthedefinitionarerequiredtobedisjointornot.
Erd˝osalsoconsideredtheproblemofgeneratingonlysetsofsizeatmosts,wheresisapositiveinteger.F¨urediandKatonainvestigatedthislatterproblemin[3].Fors≤2theproblemisvoid,andfors=3theproblemisequivalenttoTur´an’stheorem[6].Fors≤4,n≥8theyestablishthatthe
4
cardinalityofanoptimalgeneratorisn+(n2)−
difficult(NP-hard,seeSection5);ontheotherhand,theserigidrequire-mentsbringustotheprefixedconstraintsofextremalcombinatoricsversustheflexibleinputsofalgorithmicproblems.Thesequestionsleaddirectlytobeautifulandseeminglydifficultmathematicalproblems.
Thebasicproblemstudiedinthisarticlehasbeenmentionedbythefirstauthorintheactivityreportoftheproject“decisionmakingunderuncertainty”attheCentreforAdvancedStudyofOslo,in2000-2001.Con-jecture1belowisexplicitlymentionedin[1]independentlyofErd˝os[2].However,theonlyresultaboutthisproblemsofarseemstobe[3].
InSection2weintroducethemainconstructionandprovidetherelatedconjectures,remarksandsomeotherpreliminaries,includingtherelationoftheproblemtotheTur´annumber.InSection3andSection4themainresultsofthepaperandtheirproofsarepresented,whereSection3isanauxiliarysectioncollectinggeneralfactsaboutthecriticalsituationwhenforsomen,k,v,Gisnotanoptimal(n,k)generator,butG−visanoptimal(n−1,k)-generator.Finally,inSection5weshowthatnaturalrefinementsoftheprobleminthespiritofcombinatorialoptimizationareNP-hard,andproveontheotherhandthattheconstructionprovidesageneratorthatdoesneverexceedsasmallconstanttimestheoptimum.IntheAppendixweshowsomemoreresultsconcerningthecasek=2,whichenabledustofinishsomemoreconcreteparticularcasesoftheconjecture.
2Construction
Anaturalwayofconstructingageneratoristopartitiontheset[n]intokpartsandtoincludeallthenon-emptysubsetsofeachpartinthegenerator.Thecardinalityofsuchageneratorisminimumwhenthesizesofthepartsdifferbyatmostone.
Moreformally,letp:=p(n,k):=n
Forinstancewehaveconstr(13,5)=27forn=13andk=5.
Clearly,opt(n,k)≤constr(n,k),andinfacttheequalityseemstoholdalways:
Conjecture1Foralln,k∈IINthegeneratorCONSTR(n,k)isoptimal.Quitesurprisinglythisconjecturearoseinproductionmanagement,andfork=2itisaposthumusconjectureofErd˝os:
Indeed,asZolt´anF¨uredireports,Erd˝os[2],[3]askedthesameques-tionfork=2withoutrequiringthedisjointnessofthesets.Couldthesameassertionbetrueforarbitraryk?Letop(n,k)denotetheopti-mumforthisproblem.Clearly,op(n,k)≤opt(n,k)≤constr(n,k),soifop(n,k)=constr(n,k)istrueforsome(n,k),thereisequalitythroughoutforthis(n,k).Theseequalitieswouldmeanthatdisjointnessisanirrele-vantrequirement(inthesensethatitdoesnotchangetheoptimumvalue).Couldthisbeprovedbysomesimpleargumentwithoutnecessarilysettlingtheconjectures(seeConjecture7)?Inmanyresultsofthepaperopt(n,k)canbereplacedbyop(n,k),seesomeremarksattheendofSection3.
Moreover,wealsoconjecturetheunicityoftheconstruction:Conjecture2Foralln,k∈IINsuchthatp(n,k)=2,CONSTR(n,k)istheuniqueoptimal(n,k)-generator.
Tryingtoprovetheprecedingtwoconjecturesinductivelyleadstothefollowingconjecturethatwouldimplyboth(seethenextsection):
ForahypergraphG⊆P([n])andz∈[n]letG(z):={g∈G:z∈G}.Conjecture3Foralln,k∈IIN,forevery(n,k)-generatorG,thereexistsz∈[n]suchthat
|G(z)|≥2p(n,k)−1.WeprovethatConjecture3istrueforp=1,2,3and(n,k)∈{(7,2),(8,2)}forwhichp=4.
NoticethatthepartitionunderlyingtheconstructionisthesameasthatinTur´an’stheorem[6].Thetwoareactuallyrelated.TheTur´annumberT(n,s,l),wheren,s,larethreepositiveintegerswithl≤s≤n,istheminimumnumberofsubsetsofsizelofasetofsizen,suchthateachsubsetofsizescontainsatleastoneofthem.Inagenerator,sinceeverysubsetofsize(l−1)k+1mustcontainamemberofsizeatleastl,thereareatleastT(n,(l−1)k+1,l)membersofsizeatleastl.
4
Tur´ansolvedthisproblemforl=2.Ifl=2,thatiss=k+1,hisproblemcanbestatedasfollows:minimizethenumberofedgesofagraphonnverticessothatthemaximumnumberofpairwisenon-adjacentverticesdoesnotexceedk.Replacingeverymembergofageneratorbyapairwhichisasubsetofg,wealwayshavethisproperty.Tur´anprovedthattheuniqueminimumforthisnumberisgivenbykcliquesofalmostequalsizethatpartitionthevertex-set.Thispartitioncoincideswiththedefiningpartitionoftheconstruction,showingthat,thenumberofmembersofsizeatleasttwoinageneratorisatleastthenumberofsetsofsizeexactlytwoinTur´an’sconstruction.
Forl≥3,Tur´anconjecturedthatthepartitionintoblocksstillgivesthesolutiontoitsproblem,butthisappearstobefalse.AccordingtoSidorenko[5],forn=9,s=5,l=3withk=2ands=(l−1)k+15Tur´an’sconstructionprovides43+3=14subsetsofsize3sothatevery5-tuplecontainsatleastoneofthem,whereastheaffineplaneoforder3givesasolutionwithonly12subsetswiththesameproperty.ThisexamplehasbeenadoptedbyF¨urediandKatonatofindtheminimumnumberofsetsthat2-generateall4-tuplesofaset.
Indeed,forn=9,thesetofminimumsizethat2-generatesall4-tuplescanbedefinedwiththehelpoftheaffineplanewithq=3:takethelinesoftwoparallelclasses(6triplets)andthe2-elementsubsetsofthelinesforthetworemainingparallelclasses(9pairsforeach,intotal18).ThegeneratorGconsistingofthese24setsandthesingletons2-generateallthesetsofsizeatmost4.GeneralizingthisconstructionF¨urediandKatona[3]provethatitprovidesthebestestimatefor2-generatingall4-tuplesforalln.Compare24withthesizeofthesubsetofCONSTR(9,2)capabletoachievethesame554task,the2-and3-tuplesofCONSTR(9,2),43+2+3+2=30.With30sets–addtoGthe6linesoftheaffinespacethatarenotyetincludedinit–actuallythesetof5-tuplescanalsobegenerated.
Wecannotcontinueinthisdirection,sincefindingtheTur´annumberwhenl≥3isknownasadifficultopenproblem,moreoveracloserdirectlookusingmorethanjustthecontainmentsprovidesbetterlowerboundsforthediversityproblemingeneral(Section5).
3Induction
Inthissectionweshowsomegeneralfactsthatmayhelpininductiveproofsprovidedwestillhaveanoptimalgeneratorafterthedeletionofoneortwoelements.Inordertoanalysehowopt(n,k)changesasafunctionofnwe
5
needtightlowerandupperestimates.Theonlyupperestimatewehaveisconstr(n,k)andwewilluseitallthetime;inthelowerestimatestwoparametersofahypergraphwillplayarole,thedegreeandtheminimumtransversalandthelike:
ForahypergraphG⊆P([n])andasubsetZ⊆[n]wedefine:
G−ZG(Z)GZGZG/Z
:=:=:=:=:=
{g∈G{g∈G{g∩Z{g∪Z{g\\Z
:::::
g∩Z=∅}Z⊆g}g∈G}g∈G}g∈G}
OneelementsetsZ={z}areoftenreplacedbyz,whentheusageisevident.Letusseesomeexamplesofoccurrencesofz∈[n]andU⊆[n]:
G−zG/zG(z)/zG(z)−UG(z)U
=====
{g∈G{g\\{z}{g\\{z}{g∈G{g∪U
:z∈/g}=G\\G(z):g∈G}:g∈G(z)}
:z∈g,g∩U=∅}:g∈G,z∈g}
Thequantity|G(z)|isusuallycalledthedegreeofzinthehypergraphG.NotethatG(z)/z=HifandonlyifG(z)={z}H.
Wewillactuallyneedtorefineoursetsandourquantities.Forahyper-graphG⊆P([n])andp∈IIN,i=1,...p,wedenoteGi:={g∈G:|g|≥i};constri(n,k):=|CONSTRi(n,k)|.
InCONSTR(13,5)thereare13hyperedgesofsize1,11ofsize2and3ofsize3,soconstr1(13,5)=27,constr2(13,5)=14,constr3(13,5)=3;constri(n,k)−constri+1(n,k)(i=1,...,p)isthenumberofmembersofsizeexactlyi.
WeshouldnotdreamforanythingstrongerthanConjecture3,whichimpliesalreadyalltheotherconjectures.However,wemayneedmoredetailsforaproof(asitwillbethecaseforsomeofourresults):
Conjecture4Foralln,k∈IIN,forevery(n,k)-generatorGwehave:(1)
|Gi|≥constri(n,k)foralli=1,...,p.
Sinceconstr1(n,k)=constr(n,k)thisconjecturecontainsConjecture1.Whentheaveragedegreeisnotfarfromthemaximum(ifn=pkormoregenerally,whenrissmallcomparingtok)italsoimpliesConjecture3:
6
Proposition1Ifn=pkand(1)holdsforahypergraphG,thentheaveragedegreeinGisatleast2p−1,andeverydegreeisequaltothisnumberifandonlyifthereisequalityeverywherein(1).
Proof.TheaveragedegreeofGisequaltothesumofthesizesinGdividedbyn,whichinturnisequalto
1/n
ni=1
|Gi|,
sinceasetofsizesisencounteredhereforthevaluesi=1,...,s,thatis,
exactlystimes.
If(1)holds,thenthisnumberisgreaterthanorequaltotheaveragedegreeofthehypergraphCONSTR(n,k),whichisequalto2p−1,sincealldegreesareequaltothisnumber.Thereforealldegreesareequalto2p−1ifandonlyifthereisequalityeverywherein(1),asclaimed.Proposition2Foralli=1,...,p:|{g∈CONSTR(n,k):|g|=i}|=
pp−1
.+(k−r)constri(n,k)−constri+1(n,k)=r
ii
IfH⊆P([n])isahypergraph,atransversalisasetthatmeetsall
membersofH,andτ(H)denotestheminimumsizeofatransversal.IfHhasmdisjointmembers,thenclearlyτ(H)≥m.IfHcontainstheemptyset,ithasnotransversal,wedefinethenτ(H)=∞.
Generatorscanbecharacterizedintermoftransversals,bythefollowingeasybutusefulproposition:
Proposition3LetG⊆P([n])bean(n,k)-generator,andi∈{1,...,p}.Thenτ(Gi)≥k(p−i+1)−r,andthisboundistight.
Proof.SupposeGisan(n,k)-generator,andT⊆[n],|T| Theextremecasei=pofConjecture4isnoweasy,andwewillneedit: 7 Proposition4IfGisan(n,k)-generator,then|Gp|≥constrp(n,k)=k−r=n−(p−1)k,andiftheequalityholdsGcontainsexactlyk−rsetsofsizeatleastp,andtheyarepairwisedisjoint. Proof.Applytheprecedingpropositiontoi=p:|Gp|≥τ(Gp)≥k−r=n−(p−1)k,andiftheequalityholdsthroughout,theninparticular|Gp|=τ(Gp),thatis,allthesetsofGparepairwisedisjoint.WeprovenowthatConjecture3impliesConjecture1,andConjecture2. Thefollowinglemmadeducestheoptimalityoftheconstruction–thatis,Conjecture1–byinductiononnifandonlyiftherealwaysexistsanoptimalgeneratorcontainingavertexofdegreeatleast2p−1(whichissomewhatweakerthanConjecture3,seeConjecture5below.): Lemma1LetGbeanoptimal(n,k)-generator,z∈[n],|G(z)|≥2p−1,andassumeconstr(n−1,k)=opt(n−1,k).Then: |G(z)|=2p−1,constr(n,k)=opt(n,k). Proof.SinceG−zgeneratesP([n]\\{z}),itisan(n−1,k)-generator: opt(n,k)=|G|=|G(z)|+|G−z|≥2p−1+opt(n−1,k) =2p−1+constr(n−1,k)=constr(n,k) sothereisequalityeverywhere. Asaconsequence,weseethatConjecture1followsrecursivelyfor(n,k)ifweknowConjecture3forall(n,k),k≤n G−z⊆P(V1)∪···∪P(Vk) 8 forapartition{V1,...,Vk}(Vi=∅,i=1,...,k)of[n]\\{z}.Thenthereexists1≤i≤k,letitbei=1,suchthatzseesV1,moreover,ifitdoesnotstronglyseeV1,then|G(z)|≥2|V1|+m−1,wherem:=mini=2,...,k|Vi|.NotethatsinceG−zgenerates[n]\\z,infacttheequalityholdsinthecondition.IntroducethenotationU:={U⊆V1,{z}∪U∈/G}.ThenzdoesnotstronglyseeV1ifandonlyifU=∅;{z}∈Gimplies∅∈/U,andthereforeUhasanonemptymemberwhichisinclusionwiseminimal.Proof.Supposeforacontradictionthatthefirstpartofthetheoremisfalse,thatis,foralli∈{1,...,k},thereexistsαi∈P(Vi)\\(G(z)Vi).Since{z}∈Gwehave∅∈G(z)Vi,soαi=∅foralli=1,...,k. LetnowZ:={z}∪α1∪···∪αk.ThesetZisgeneratedbyatmostkmembersofG,exactlyoneofwhich,–denoteitbyg–containsz.Clearly,g∩Vi⊆αi,andg=αibecauseofthedefinitionofαi(i=1,...,n).SoZ\\gstillcontainsanelementfromeachVi(i=1,...,k),andthereforecannotbegeneratedbyatmostk−1membersofG−z⊆P(V1)∪···∪P(Vk).Thiscontradictionprovesthefirstpartofthetheorem.Thatis,wecannowassumeG(z)V1=P(V1),defineUlikebeforetheproof,andnote:ifg∈G(z),g∩V1=U∈Uthengmeets[n]\\(V1∪z). Toprovethestrongerinequalityofthetheorem,letU∈UbeminimalinU;asnotedU=∅.Define G=U:={g∈G(z):g∩V1=U}=G(z∪U)−(V1\\U),and GU:={g∈G(z):g∩V1U}=(G(z)−(V1\\U))\\G=U.Clearly,G=U∩GU=∅.Letτ:=τ(G=U/(U∪z)),thatis,τistheminimumsizeofasetdisjointofU∪zthatmeetseachmemberofG=U.Thisminimumisfinite,sinceasnoted,eachmemberofG=UhasanelementoutsideU.Notealsothat|H|≥τ(H)holdswheneverthelatterisfinite.Thereforewecansupposeτ andnothingelseremainstobeproved.Claim:|GU|≥2|U|+2m−τ−2. SinceU∈Uisminimal,z(P(U)\\U)⊆GU,soweknowalready2|U|−1elementsofGU.ItsufficestoshownowthatGUhasatleast2m−τ−1elementsthatmeet[n]\\V1. LetCbeatransversalofG=U/(U∪z),|C|=τ.ThenC⊆V2∪...∪Vk.NowtheconditionofthetheoremissatisfiedforG−((V1\\U)∪C),with 9 thesamez,andwiththepartition{U,V2\\C,...,Vk\\C}:wealreadyknowU=∅,andbecauseof|C|=τ UsingthatzseesV1,andthenapplyingtheClaimandtheinequality2m−τ≥m−τ+1weget: |G(z)|=|G(z)\\(G=U∪GU)|+|G=U|+|GU|≥2|V1|−2|U|+τ+2|U|+2m−τ−2≥ ≥2|V1|+τ+(m−τ+1)−2=2|V1|+m−1. Theequalitycaseoftheboundsisworthanalyzingalsoinhopeofgainsintheestimates:thegainsallowtodeducestrongerboundsonthedegreefromweakerbound,andtherewiththeoptimalityofCONSTR(n,k)forsomenandk.InthefollowinganalysisandcorollarywewillsupposeG⊆P([n])isan(n,k)-generator,z∈[n],andG−z⊆P(V1)∪···∪P(Vk)forapartition{V1,...,Vk}(Vi=∅,i=1,...,k)of[n]\\{z};wedenoteµ,mthesmallestandthesecondsmallestsizeamongthesizes{|Vi|:i=1,...,k}ofthepartitionclasses. Undertheconditionofthetheoremafirstestimateis|G(z)|≥2µ,sincezseesoneoftheclasses.Thetheoremclaimsthatthereisequalityinthisboundifandonlyifzstronglyseesoneofthesmallestclasses. Itisinterestingthattheboundjumpsfrom2|V1|to2|V1|+m−1ifzseesV1butdoesnotstronglyseeit.Whataretheconditionsoftheequalitythen? Proposition5SupposeG⊆P([n])isan(n,k)-generator,z∈[n],andG−z⊆P(V1)∪···∪P(Vk)forapartition{V1,...,Vk}(Vi=∅,i=1,...,k)of[n]\\{z}.IfzseesV1butdoesnotstronglyseeit,thatis,U=∅,thentheequalityholdsinthebound(ineq2) |G(z)|≥2|V1|+m−1, ifandonlyifthereexists1≤i≤k,letitbei=2suchthat|V2|=m,V2=:{v1,...,vm}andchoosingtheindicesappropriately,oneof(i)-(iii)istrue: 10 (i)ThereexistsU⊆V1suchthatwithU1:=(P(U)\\{U})andU2= {U∪{vi}:i=1,...,m},orU2={U∪{vi}:i=1,...,m−1}∪{{vm}}, G(z)/z=U1∪U2. (ii)m=2,U⊆P(V1)isarbitrary,g=U:=U∪{v1}(U∈U),and G(z)/z=(P(U)\\U)∪{g=U:U∈U}∪{v2} (iii)m=1,Uisarbitrary,andG(z)/z=(P(U)\\U)∪{g=U:U∈U},where g=UistheunionofUandanarbitrarynon-emptysetofelementsthatformsingletonclasses.Proof.SupposetheconditionofTheorem1issatisfied,and(ineq2)issatisfiedwithequality.Thenm≤τ,sincem>τwouldimplythat(ineq1)wouldalsobesatisfiedwithstrictinequality,andthensowouldbetheidentical(ineq2).Tohaveequalityintheclaim,G(z)cannotcontainasetthatmeetsapartition-classofsizebiggerthanmdifferentfromV1. ConsidernowUasintheproof,andletU∈U.Letusnowexploittheequalitiesintheinequalitiesoftheproofof(ineq2)intheproofofTheorem1fromtheendbackwards:inordertohaveequalityin(ineq2),weneed2m−τ=m−τ+1,andsincem−τ≥0,thisholdsifandonlyifm−τ=1,orm−τ=0.Wewillhavetoconsiderboththecaseτ=mandτ=m−1. Ifm>2then|G=U|>1forallU∈U,whilein(ineq1)weusedtheboundof1forallbutoneU∈U.Sothestrictinequalityholdsif|U|>1.If|U|=1theequalitycanhold,andthetwocasescorrespondingtoτ=mandτ=m−1arelistedin(i). Ifm=2andτ=m,thenagain,|G=U|>1forallU∈U,andthestrictequalitycanholdonlyif|U|=1,includedalreadyinthepreviouscase.However,ifm=2andτ=m−1,then|G=U|=1ispossibleforallU∈U,andpreciselyiftheuniqueelementofG=UistheG=Uof(ii).Soallthenewcaseswhereequalitycanoccurform=2arelistedin(ii). Ifm=1,thenasnoticed,allsetsinG(z)mustbeincludedintheunionofV1andthepartitionclassesofsizem,thatis,mustbeoftheformgivenin(iii).Itiseasytocheckthatthisisthensufficient:allsetsofthisformare(n,k)-generators.Wegetthefollowingcorollaryfromthetheoremandtheaboveanalysisoftheequality.Recallthenotationspandm. 11 Corollary1G⊆P([n])isan(n,k)-generator,z∈[n],andG−z⊆P(V1)∪···∪P(Vk)forsomepartition{V1,...,Vk}(Vi=∅,i=1,...,k)of[n]\\{z}.Then(ineq3) |G(z)|≥2p−1+m unlesszstronglyseesoneoftheclasses,oroneof(i),(ii),(iii)holds.Thefollowinglemmastatesinadditiontotheoptimalityofthecon-structiontheunicityofoptima–thatis,Conjecture2–byinductiononnifandonlyifeveryoptimalgeneratorcontainsavertexofdegreeatleast2p−1(whichisstillsomewhatweakerthanConjecture3,seeConjecture6):Lemma2LetGbeanoptimal(n,k)-generator,z∈[n],|G(z)|≥2p−1andp≥3;assumethatCONSTR(n−1,k)istheuniqueoptimal(n−1,k)-generator.ThenG=CONSTR(n,k). Proof.ByLemma1,|G(z)|=2p−1,and|G|=constr(n,k),whenceG−z=constr(n,k)−2p−1=constr(n−1,k),andthenbythecondition,G−z=CONSTR(n−1,k). SoG−z=(P(V1)∪···∪P(Vk))\\{∅},where{V1,...,Vk}isapartitionof[n]intopartsofsizep(n,k)andp(n,k)−1.ByTheorem1onecanchooseV1sothateitherG(z)/z=P(V1),or|G(z)|≥2|V1|+m−1withm=mini=2,...,k|Vi|=p(n,k)−1≥2. Inthefirstcase,byoptimality,V1isaclassofsizep(n,k)−1sothatG=CONSTR(n,k)follows.Ifindirectly,thesecondcaseholds,then 2p−1=|G(z)|≥2p−1+m−1≥2p−1+1, andthiscontradictionfinishestheproof. Modifiedasfollows,Conjecture3becomesequivalenttoConjecture1byLemma1. Conjecture5Foralln,k∈IINthereexistsanoptimal(n,k)-generatorGandz∈[n]suchthat:(2) |G(z)|≥2p(n,k)−1. Modifiedasfollows,Conjecture3becomesequivalenttoConjecture2byLemma2. 12 Conjecture6Foralln,k∈IIN,foreveryoptimal(n,k)-generatorGthereexistsz∈[n]suchthat(2)holds. Wehavethusthefollowingimplicationbetweentheconjectures:Conjecture3=⇒Conjecture2=⇒Conjecture1,Conjecture4=⇒Conjecture1Conjecture1⇐⇒Conjecture5,Conjecture2⇐⇒Conjecture6. Letusalsostatetheconjectureassertingthatthedisjointnessrequire-mentdoesnotchangetheoptimumvalue. Conjecture7Foralln,k∈IIN:op(n,k)=opt(n,k). SofarallthesimplePropositions,LemmasandConjecturesholdwithoutchangeifdisjointnessisnotrequiredandopiswritteninsteadofopt.ThisisnottruethoughforTheorem1anditscorollaries,includingLemma2andProposition5,thereasonbeingthatweusedinanessentialwaythatatmostoneofthekdisjointsetscontainsagivenz∈[n]. 4Casep≤3 Recallthenotationp=p(n,k)=n caseofequality.Thereasonforthisisnothingmorethanthevalidityof2p−1+m−1=2p−1inthiscase. Thisisalsotheonlycasewhen“Tur´an’sbound”T(n,k+1,2)isexact.Proof.LetGbeanarbitrary(n,k)-generator.Itcontainsallthesingletons,andifp=1,thatis,n≤kthereisnoneedofmoremembers. Ifp=2,thatis,k+1≤n≤2k,thenbyProposition4,|G2|≥constr2(n,k)=k−r=n−k,andtheequalityholdsifandonlyifthesetsofsizeatleast2aredisjoint. Conversely,supposethehypergraphGhasn−kdisjointmembersofsizeatleast2(k+1≤n≤2k),andletuscheckthatitisan(n,k)-generator.LetS⊆[n],s:=|S|>k.ThenSmissesatmostn−s Nowweprove(1)fori=2,byinductiononn−2k.ByTheorem2itistrueforn=2k.Forthesakeofeasierunderstanding,wefirstdotheproofseparatelyforn=2k+1,usingitforn=2k:Forallz∈[2k+1]wehave|G2−z|≥constr2(2k,k)+1=k+1,otherwisewearedonebyLemma2.Now |G2−z|≥(2k+1)(k+1), z∈[n] usedherethatmultiplyinganumberxby andinthissumeverymemberofG2iscountedatmost2k−1times,so|G2|≥2k+1k−1/2(k+1)>k+2.(Foraneasierlookatitwe k+1/2 n−2 (opt(n−1,k)−(n−1)+1)>opt(n−1,k)−(n−1)+2, > n−2 sinceopt(n−1,k) WedonotseehowtodeduceConjecture3fromtheabovetheorem.Ontheotherhand,wecanprovethisconjectureseparately(forp=3),implyingtheprevioustheoremaswell,inasimplerway,andwithoutusinganyofthepreviousresultsorthedisjointnessofgenerators.(Fori=3(2)iseasy,andthefollowingtheoremimpliesitfori=2andi=1.For2k≤n≤3kwewillthushavetwoproofsoftheoptimality.(Westillincludedtheprevioustheorembecauseitforecastsourfuturedifficulties:whenevertheaveragedegreeofCONSTR(n,k)ismuchsmallerthanthemaximumdegree,“averagingarguments”donoteasilywork.) Theorem4Ifp=3,thatis2k Wecansupposewithoutlossofgeneralityn=2k+1.Indeed,ifn>2k+1,thenwecanapplytheprovenassertiontothe(2k+1,k)-generatorG(U),whereU⊆[n],|U|=2k+1. LetGbean(n,k)-generator,andsupposeforacontradiction|G2(z)|≤2forallz∈[n]. WedefineanundirectedgraphG=(V,E)onV:=[n]=[2k+1],inthefollowingway:foreachg∈G,|g|≥2,wechoosetwoverticesu,v∈g,lete=uv∈E,andusethenotationgeforg.Forg1=g2∈Gwecantakethesameu,v(ifu,v∈g1∩g2),butthenwetaketwoparalleluvedgese1ande2.Wewillsaythattheedgee=uvrepresentsge∈G.WethussupposethatdifferentsetsinGarerepresentedbydifferentedges.Furthermore,wesupposethatwemakethepossiblechoicesofuandvsoastominimizethenumberofcomponentsofG. NowitfollowsfromtheindirectassumptionthatallthedegreesofthegraphGareatmost2,soitisadisjointunionofcycles,pathsandisolatedvertices.ThefollowingClaimisthekeyoftheproof: Claim:LetCbeacycleofG,andeanedgeofC.Thene∈G,andisnotcontainedinanybiggersetofG. Indeed,bythedefinitionofG,eiscontainedinasetofG,soitissufficienttoprovethatnosetinGcanproperlycontaine. –Ifanextraelementzofge(differentfromtheendpointsofe)ofsuchasetwereinC,thenzwouldbecontainedinthreedifferentsetsof 15 G:gaandgb,wherea,barethetwoedgesincidenttozinC,andge⊇e∪{z}.Clearly,e,a,baredifferent,andthereforege,ga,gbaswell,contradictingtheindirectassumption. –Ifanextraelementzofge(differentfromtheendpointsofe)ofsuchasetwereinanothercomponentKofG,thenreplacingoneoftheendpointsofebyapointinge∩K,wegetanotherrepresentationofGwithonelesscomponent(allverticesofCandKarenowinthesamecomponent),contradictingthedefinitionofG.Theclaimisproved. LetUbethesetofverticesofGthatareinacycle.ThesubgraphG(V\\U)containsonlypathsandisolatedvertices,sowecanfindastableset(notcontainingbothendpointsofanedge)SofG(V\\U)suchthat|S|≥|V\\U|/2.(Wetakea(the)biggerstablesetineachcomponent.) WeshownowthatS∪Ucannotbek-generated,contradictingthechoiceofG.Recallthatanyg∈G,g⊆ShasalsoanedgeinG.ButtheonlyedgesinS∪Uareinthecycles,andforthesetheclaimholds.ThereforewhatwehavetoshowisexactlythatS∪UisnottheunionofatmostkedgesofGorsingletons. Indeed,denoteγ(X)theminimumnumberofedgesandsingletonsnec-essaryforgeneratingasetX⊆n.LetthecomponentsofGbeC1,...,Ct(t∈IIN).Notethatforalli=1,...,t:γ(U∩Ci)≥|Ci|/2.Then γ(U)= ti=1 γ(U∩Ci)≥ ti=1 |Ci|/2= 2k+1 complexity,andsimplebutsurprisinglygoodestimatesforthequantityopt(n,k). Twonaturaloptimizationproblemsarise: –Wedonotwanttogenerateallcars,thatis,allsubsetsofoptions,justapre-givenfamily.–Thegeneratorisrestrictedtochooseelementsfromagivenhyper-graph.Moreprecisely: PROBLEM:CHOOSYCUSTOMER’SDIVERSITYInput:C⊆P([n]),numbersk,s. Question:DoesthereexistG⊆P([n])thatk-generatesallsetsinC,and|G|≤s. PROBLEM:CONSTRAINEDPRODUCER’SDIVERSITYInput:H⊆P([n]),numberkandatarget-setT⊆[n].Question:DoesthereexistG⊆Hthatk-generatesT? Notethatinthissecondproblemweonlyspeakabouttheexistenceofagenerator.Thesearejusttwosimpleandnaturalvariantsthatwechooseforthesakeofexamples.ThereadermayenjoystatinghisfavoritevariantsandcheckingNP-completenessforthem. Theorem5BothCHOOSYCUSTOMER’SandCONSTRAINEDPRO-DUCER’sDIVERSITYproblemsareNP-complete. Proof.WefirstreduceVERTEXCOVERtoCHOOSYCUSTOMER’SDIVERSITY,andeventoinstanceswherek=2.(VERTEXCOVERand3DMbelowareprovedtobeNP-completeinGareyandJohnson’sseminalbook[4].) LetG=(V,E)beagraph,andconsidertheproblemwithinputΩ=V∪{u},whereuisanextravertexnotinV,andC:={{v}:v∈Ω}∪{{a,b,u}:a,b∈V,ab∈E}. ClearlyifTisavertexcover,thatisT∩e=∅foralle∈E,thenG:={{v}:v∈Ω}∪{{t,u}:t∈T}does2-generateallC∈C.Conversely,{{v}:v∈Ω}mustbecontainedinallgenerators,andalltheothersetscanbesupposedtocontainuandtobeofsize2.(Otherwisewecanadduandkeeponlyoneoftheelementsdifferentfromu.)LetT:={v∈V:(v,u)∈G}.ThenTisavertexcover,finishingtheproofofthefirstassertion. 17 Letusnowreduce3DMtoCONSTRAINEDPRODUCER’SDIVER-SITY.Let(U,V,W,E)beaninstanceof3DM,thatis,E⊆U×V×W(theCartesianproductofU,V,W),where|U|=|V|=|W|=3k.DefineT:=U∪V∪W.Nowclearly,G⊆Ek-generatesTifandonlyifitisa3-dimensionalmatching(thatis,ifandonlyifitpartitionsT).Inbothproofsitisirrelevantwhetherweaskdisjointnessornotfromthegenerators.(Inthesecasesthereexistsalwaysadisjointoptimalsolution.) Wenowshowthattheconstructionprovidesaquitegoodapproximationoftheoptimum.Enumerationprovidestheboundconstr(n,k)≤opt(n+2k,k).Letussketchaproofofthis.Givenan(n,k)generatorG,allthe2n−1nonemptysubsetsof[n]canbeencodedbyanatmostkelementsubsetofG: k|G| ≥2n−1.iItfollowsthatk|G|k/k!thatis,|G|k≥(k−1)!2n,andapply-ingStirling’sformulaandtakingthek-throot:|G|≥k−1 n/k,whileconstr(n,k)≤k2n/k+const,whichshowsthate2 constr(n,k)/opt(n,k)doesnotexceedε(n,k)ewherelimn,k→∞ε(n,k)=1.Theexacttresholdvalidforallnandkiscertainlysmallerthan4:constr(n,k)≤4opt(n,k).Sinceconstr(n+2k,k)≥4constr(n,k),wegotthatconstr(n,k)≤opt(n+2k,k). ForsmallkwedonothavetoapplyStirlingformulaandwegetessen-|G| tiallybetterbounds:fork=2,weget|G|+2≥2n−1andwegetthesameboundsasinthetheoremsbelow.Stillwiththesamemethod,fork=3wegetthattheconstructionisatmost4=1,747···timesthe 12 optimum.Letusdeducetheresultsfork=2withanothermethodaswell,whichwillalsoleadtoasimplegeneralpropositionforarbitraryk:Theorem6Foralln∈IIN: opt(n,2)≤constr(n,2)≤3/2opt(n,2), √ andtheconstant3/2canactuallybeimprovedto 2/2ifniseven. Proof.LetGbean(n,2)-generator.Sinceeverysubsetof[n]containingzistheunionofasetinG(z)andasetin(G−z)∪{∅},wehave: |G(z)|(|G−z|+1)≥2n−1. 18 i=1≥2n, Theminimumofx+y,(x,y∈IR)undertheconditionxy=2n−1isx= n−1 y=2 2 n+1 +2 n−1 2 2 −1+2 n −1+2 Bytheinequalitybetweenthegeometricandarithmeticmeans,wehaveunderthiscondition n−k (ineq4)|G(s)|≥k2 s∈S ,andthemem-bersof∪s∈SG(s)generates∈S|G(s)|sets;thelatterconditionholdsifandonlyifanypairofsetsfromdifferentG(s)aredisjoint. n−k Defineforalls∈S,Ps:=∪G(s).Becauseof|G(s)|=2 k,thatis, k s∈S |Ps|≥k( n−k foralls∈S. Wehavearrivednowtoourfinalestimationoneingredientofwhichis(ineq4),andtheotheristheobviousinequality|G−S|≥opt(n−k,k).Then opt(n,k)=|G|=|G−S|+|G(s)|≥opt(n−k,k)+k2p−1= s∈S k +1=n/k=p =constr(n−k,k)+k2p−1=constr(n,k). Soopt(n,k)=constr(n,k),andthereisequalityeverywhere,soG−Sisoptimal.IfCONSTR(n−k,k)istheuniqueoptimal(n−k,k)-generatorthenG−SisisomorphictoCONSTR(n−k,k).Finally,applyingLemma2ktimesonebyonetotheelementsofsintheroleofz,weseethatG=CONSTR(n,k).Conclusion:Weprovedthatthemostnaturalconstructionforan(n,k)-generatorisoptimalifn≤3k,andforsomeotherindividualpairs(n,k),regardlesswhetherthedisjointnessofthesetsisrequired,moreover,itisalwaysaconstanttimeapproximationwithasmallconstant.ThenaturalformulationsasanoptimizationproblemareNP-hard. 20 APPENDIX:k=2andcanwegofurther? Wededucetheconjecturefortwomorecases,alsoinordertoprovideanotherexampleofapplyingtheargumentsandassertionsofthepaper,andtorealizethelimitsofsomearguments. ThefollowinglemmaextendsthevalidityofTheorem1tothecasewhenG−zcancontainonemoresetbesidessubsetsofthepartition-classes.Werestrictourselvestothecasek=2(thestatementanditsuseseemtobeconsiderablymorecomplicated(evenifnothopeless)fork>2): Lemma3SupposeGisan(n,2)-generator,(G−z)⊆P(V1)∪P(V2)∪{h},where{{z},V1,V2}(z∈[n])isapartitionof[n],2≤µ:=|V1|≤|V2|(i=1,2),h⊆V.Then|G(z)|≥2µ,inparticular,Gisnotoptimal.Ofcourse,wecansupposewithoutlossofgeneralityh∩Vi=∅(i=1,2),otherwisehcanbeomittedfromG,andtheassertionfollowsfromTheorem1. Proof.IfzseesV1orV2wearedone,sowesupposeitdoesnot. Claim:Forbothi=1andi=2,thereisatmostonesubsetofVithatisnotinG(z)Vi. Supposeforacontradictionthatthestatementdoesnotholdsayfori=2:letB=C⊆V2,B,C∈/G(z)V2.SincezdoesnotseeV1,thereexistsA⊆V1,A∈/G(z)V1.Weshowthen|G(z)|≥2|V1|. Thesets{z}∪A∪B,{z}∪A∪Cmustcontainhthatmustparticipatein2-generatingthesesets,whence {z}∪(A∪B)\\{h},{z}∪(A∪C)\\{h}∈G. Weshownowthat|G(z)|≥2V1,bylabellingeachsubsetofV1withadifferentsetinG(z). IfU⊆V1,U∈G(z)V1,welabelUwithanarbitraryg∈G(z),g∩V1=U.Forinstancewelabel∅with{z}.IfA∈/G(z)V1,wesawthatthereexisttwosets,{z}∪(A∪B)\\{h},{z}∪(A∪C)\\{h}∈G.AtmostoneofthemisthelabelofA\\{h},theother,say(A∪C)\\{h}isapriorinotalabel,sinceitmeetsV1alsoinA\\{h},butitisnotthelabelofthisset.LetthelabelofAbe(A∪C)\\{h}.Clearly,thelabelofadifferentsetA⊆V1,A∈/G(z)V1isdifferent,sinceitisA∪C\\{h},differentfromA∪C\\{h}.(BothA∪CandA∪Ccontainh.)Theclaimisproved.Theclaimimpliesthat|G(z)|≥2|V1|−1,butwearestillfightingforthestrictinequalityhere.Let1∈h∩V1,2∈h∩V2.ByTheorem1,zsees 21 V1\\{1}andV2\\{2}(sinceitdoesnotseeV2andV1).Ifitstronglyseesbothofthem,thenz(V1\\{1}),z(V2\\{2})⊆G,andtheonlycommonelementofthesetwoisz,sotheboundislargelysatisfied.Ifnot,theninTheorem1theequalityisnotsatisfied,sothereexistsA⊆V1andf,g∈GsuchthatA=f∩V1=g∩V1forf=g∈G,sotheequality|G(z)|=2|V1|−1doesnothold.Theorem8Forany(notnecessarilyoptimal)(7,2)-generator,(1)holds,andCONSTR(7,2)istheuniqueoptimalgenerator. Proof.Wefirstprovethesecondassertion.LetGbeanoptimal(7,2)-generator.Then|G|≤constr(7,2).AddtoGsomenewsetstogeta ˆwith|G|ˆ=constr(7,2)=22.ObviouslyGˆisstillagen-hypergraphG ˆ=CONSTR(7,2).Indeed,thenerator.ItsufficestoprovenowthatG ˆ=GfollowssinceGˆdoesnotcontainanyothergenera-CONSTR(7,2)=G torproperly.ˆ(x)betheaveragedegreeofG.Clearly(asbefore,Letd:=1/nx∈[n]GseeProposition1):(ineq5)Claim1:d>6 ˆ1|≥22andtherefore|Gˆ2|≥15aswell.AttheotherWealreadyknow|G ˆ4|≥1isobvious,letA∈Gˆ4.Weshow|Gˆ3|≥5.extreme|G ˆ3(z)|≥2,thenapplyProposition3after–Ifthereexistsz∈/A,|G ˆ3−z|≥τ(Gˆ3−z)≥2.Butthisboundisself-improving:deletingz:|G ˆ3−z,andtherefore|A|≥4,soAisnotdisjointoftheothersetinG ˆ3−z|≥τ(Gˆ3−z)+1≥3.Butthen|Gˆ3(z)|+|Gˆ3−z|≥2+3=5.|G dn= ˆ(x)|=|G |g|= ni=1 x∈[n] ˆg∈G ˆi.G ˆ3(z)|≥3,thensimilarly,applysimply|Gˆ3−z|≥–Ifthereexistsz∈A,|Gˆ3)−z≥2toget|Gˆ3(z)|+|Gˆ3−z|≥3+2=5.τ(G –Oneoftheprecedingcasesholds,becauseotherwiseeveryz∈[n]is ˆ3\\{A},althoughthereareatcoveredbyatmostonememberofG least3setsofsizeatleast3inthishypergraphon7elements.Weconcludenowtheproofoftheclaimby(ineq5): 22 d≥ 22+15+5+1 7 >6. ˆ(x)|≥7,thatis,|Gˆ−x|≤Accordingtotheclaimthereexistsx∈[n],|G 22−7=15=constr(6,2)+1.Ifthestrictinequalityholds,wearedoneby ˆ(x)|=7.Lemma2,sowecansuppose|G NowProposition1canbeappliedforn=6,k=2,p=3:thereexists ˆ(z)−x≥2p−1+1.So|Gˆ−{x,z}|≤constr(5,2),andthez∈[n],G equalityholdsherebyTheorem2.NowTheorem1canbeappliedtodeduce ˆ−{x,z},sincem=3.Sothatzstronglyseestheclassofsize2ofG ˆ−xcontainsahypergraphisomorphictoCONSTR(6,2),meaningthatitG isexactlyCONSTR(6,2)andonemoreelementh.WeconcludenowthesecondpartofthetheoremwithLemma3substitutingzforx. LetnowGbeanarbitrary(7,2)-generator.Bythealreadyprovenpartwehave(1)fori=1andi=2.Itisalsoobviousfori=4;asabove,denoteA∈G4.Inexactlythesamewayasweproceededabove,wecanget|G3|≥5,afterwhichitisstillpossibletodoonemoreself-improvingstep,toprove|G3|≥6=constr3(7,3),asclaimed: Supposeforacontradiction|G3|≤5.AsetT∈G,|T|=3willbecalledatriangle. Claim2:If|G3(z)|≥3thenG3−zhasexactlytwodisjointtriangles,andthesepartition[n]\\z. Indeed,|G3−z|≥τ(G3−z)≥2,andifoneofthesetwoinequalitiesisstrict,thenwearriveatthecontradiction5≥|G3|=|G3(z)|+|G3−z|≥3+3=6. TheaveragedegreeofG3isatleast 4+3+3+3+3 ItfollowsthatAmeetsoneofT3andT4andnotonlyinz.Indeed,|A\\{z}|+|T3\\{z}|+|T4\\{z}|≥3+2+2=7>6=|[n]\\{z}|.Letthiselementbex∈A∩T3\\{z};sincex∈T1∪T2,wecanassumeforinstancex∈T1. Nowagain,Claim2canbeappliedtox,andsince|G3|≤5,bothtrianglesofG−xarealreadyamongthelistedsets.ThesecanbeonlyT2andT4,inparticularT4isalsoatriangle. SoT4=(T1\\{x})∪{z}.BecauseofClaim3,T3contains,besidesx∈T1alsoanelementofT2.Finally,A={x,z}∪(T2\\T3),sinceanyotherelementinAwouldagaincontradictClaim2.ItfollowsthatG4={A}.Inorderto2-generate{1,2,3,4,5,6,7}itself,weneedasetinG4anditscomplement.ButthecomplementofAisdifferentofallofT1,T2,T3,T4,soG3hasasixthelement,andthisfinalcontradictionfinishestheproofofthetheorem.Corollary2Forany(notnecessarilyoptimal)(8,2)-generator,then(1)holds,thereexistsz∈[n]suchthat(2)holds,andCONSTR(8,2)istheuniqueoptimal(8,2)-generator. Proof.|G4|≥2isobviousasusually(sinceeach7elementsetstillcontainsg∈G,|g|≥4). |G3−z|≥8constr3(7,2)=48, z∈[n] andeverysetofG3hasbeencountedatmost5timesinthissum,so|G3|≥48/5=10=constr3(8,2). Itisnoweasytoprove|G2|≥constr2(8,2)(andthesame|G1|≥constr1(8,2)),withthesameargumentasintheproofofthepreviousthe-ˆwith|G|ˆ=constr(8,2)=30isnothingelsebutorem:itsufficestoproofG ˆhasanelementofCONSTR(8,2),andforthisitsufficestoprovethatG degree23=8.Sotheonlyremainingassertiontoproveisthatforany(8,2)-generatorwith|G|=constr(8,2)=30thereexistsz∈[n]suchthat(2)holds.ThenthelastassertionalsofollowsbyLemma2.LetGbesuchan(n,k)-generator.ˆ(x)betheaveragedegreeofG.Clearly(asbefore,Letd:=1/nx∈[n]GseeProposition1):d=1/n |G(x)|=1/n |g|=1/n 24 ni=1 x∈[n] ˆg∈G |Gi|=1/8(30+22+10+1)>7, finishingtheproofofthecorollary. Notethatforthislaststatementamuchweakerboundissufficient,namelythefirsteasyestimateof|G3|withouttheworksomeone. InCONSTR(8,2)theaveragedegreeisequaltothemaximumdegreeandthesamecouldbeprovedfortheoptimumgenerator,thatiswhyCorollary2includesConjecture3.Thesamecanbeprovedforarbitraryevennandk=2,buttheoddncasewith“small”averagedegreeremainsopen.Aknowledgment:WeareindebtedtoNicolasTrotignonforusefuldiscus-sions,amongthemtohavenoticedthevarietyofoptimalgeneratorswhenp=2.WealsothankZolt´anF¨urediforconnectingustothecurrentstateofthesubject. References [1]C.DaCunha,Definitionandinventorymanagementofsemi-finished productsinanAssemblyToOrdercontext(inFrench),PhDThesis,INPG,Grenoble(2004).[2]P.Erd˝os,privatecommunicationmentionedin[3](1993). [3]Z.F¨urediandG.O.H.Katona,2-basesofquadruples,Combinatorics, ComputingandProbabality15(2006),131-141.[4]M.R.GareyandD.S.Johnson,ComputersandIntractability:AGuide totheTheoryofNP-Completeness,FreemanandCompany,NewYork,1979.[5]A.F.Sidorenko,WhatweknowandwhatwedonotknowaboutTur´an numbers,GraphsCombin.11(1995),179-199.[6]P.Tur´an,Onanextremalproblemingraphtheory,(inHungarian), Math.Fiz.Lapok48(1941),436-452. 25 因篇幅问题不能全部显示，请点此查看更多更全内容