DiscreteMathematics308(2008)2002–2010 www.elsevier.com/locate/disc Note The reconstruction conjecture and edge ideals Kia Dalilia,1, Sara Faridia,2,Will Travesb,3 aDepartmentofMathematicsandStatistics,DalhousieUniversity,CanadaB3H3J5 bDepartmentofMathematics,U.S.NavalAcademy,21402,USA Received13December2006;receivedinrevisedform30March2007;accepted18April2007 Availableonline6May2007 Abstract GivenasimplegraphGonnvertices,weprovethatitispossibletoreconstructseveralalgebraicpropertiesoftheedgeideal fromthedeckofG,thatis,fromthecollectionofsubgraphsobtainedbyremovingavertexfromG.Thesepropertiesincludethe Krulldimension,theHilbertfunction,andallthegradedBettinumbers(cid:2)i,j wherej<n.Wealsostatemanyfurtherquestionsthat arisefromourstudy. ©2007ElsevierB.V.Allrightsreserved. MSC:05C60;13F55 Keywords:Reconstructionconjecture;Edgeideals;Hilbertfunction;GradedBettinumber 1. Introduction The graphreconstructionconjecture,posedbyKellyandUlamin1941(see[1]),saysthateverysimplegraphGon n(cid:2)3verticesisdeterminedbythecollectionofsubgraphsobtained,uptoisomorphism,bydeletingonevertexfrom G;thiscollectioniscalledthedeckofG,andeachvertexdeletedsubgraphiscalledacard.Thisconjecturehasproved notoriously difficult, and has motivated a large amount of work in graph theory. It is known, for example, that trees arereconstructible,asareallgraphsofupto11vertices,andalldisconnectedgraphs.Itisalsoknownthatalmostall graphsarereconstructiblefromthreecarefullychosencardsfromtheirdeck.Bondy[1]summarizestheworkdoneon thisproblem. Inrecentyears,muchworkhasbeendoneonstudyinggraphsfromanalgebraicpointofview.Theedgeidealofa simplegraphistheidealgeneratedbycertaindegreetwomonomials,whereeachmonomialistheproductofthetwo verticesjoinedbyanedgeofthegraph.EdgeidealswereintroducedbyVillarreal[9,10],whousedthecombinatorial propertiesofgraphstoproducealgebraicstatements.Inparticular,VillarrealandhiscoauthorsstudiedReesringsand Cohen-Macaulaypropertiesofedgeideals[9,10,8].Hà,RothandVanTuyl[4,7],amongothers,havestudiedresolutions ofedgeideals,findingrecursivemethodstocomputeBettinumbersforspecialclassesofgraphs. 1TheauthoracknowledgesthesupportofAARMS. 2TheauthoracknowledgesthesupportofNSERC. 3TheauthoracknowledgesthesupportofNARCandONR. E-mailaddresses:[email protected](K.Dalili),[email protected](S.Faridi),[email protected](W.Traves). 0012-365X/$-seefrontmatter©2007ElsevierB.V.Allrightsreserved. doi:10.1016/j.disc.2007.04.044 Report Documentation Page Form Approved OMB No. 0704-0188 Public reporting burden for the collection of information is estimated to average 1 hour per response, including the time for reviewing instructions, searching existing data sources, gathering and maintaining the data needed, and completing and reviewing the collection of information. Send comments regarding this burden estimate or any other aspect of this collection of information, including suggestions for reducing this burden, to Washington Headquarters Services, Directorate for Information Operations and Reports, 1215 Jefferson Davis Highway, Suite 1204, Arlington VA 22202-4302. Respondents should be aware that notwithstanding any other provision of law, no person shall be subject to a penalty for failing to comply with a collection of information if it does not display a currently valid OMB control number. 1. REPORT DATE 3. DATES COVERED 30 MAR 2007 2. REPORT TYPE 00-00-2007 to 00-00-2007 4. TITLE AND SUBTITLE 5a. CONTRACT NUMBER The reconstruction conjecture and edge ideals 5b. GRANT NUMBER 5c. PROGRAM ELEMENT NUMBER 6. AUTHOR(S) 5d. PROJECT NUMBER 5e. TASK NUMBER 5f. WORK UNIT NUMBER 7. PERFORMING ORGANIZATION NAME(S) AND ADDRESS(ES) 8. PERFORMING ORGANIZATION United States Naval Academy (USNA),Mathematics REPORT NUMBER Department,Annapolis,MD,21402 9. SPONSORING/MONITORING AGENCY NAME(S) AND ADDRESS(ES) 10. SPONSOR/MONITOR’S ACRONYM(S) 11. SPONSOR/MONITOR’S REPORT NUMBER(S) 12. DISTRIBUTION/AVAILABILITY STATEMENT Approved for public release; distribution unlimited 13. SUPPLEMENTARY NOTES 14. ABSTRACT see report 15. SUBJECT TERMS 16. SECURITY CLASSIFICATION OF: 17. LIMITATION OF 18. NUMBER 19a. NAME OF ABSTRACT OF PAGES RESPONSIBLE PERSON a. REPORT b. ABSTRACT c. THIS PAGE Same as 9 unclassified unclassified unclassified Report (SAR) Standard Form 298 (Rev. 8-98) Prescribed by ANSI Std Z39-18 K.Dalilietal./DiscreteMathematics308(2008)2002–2010 2003 Ourgoalinthispaperistoconsiderthereconstructionofalgebraicinvariantsassociatedtotheedgeidealofasimple graph.Aninvariantofagraphissaidtobereconstructibleifitcanbedeterminedfromitsdeck.Forexample,letGbe agraphonnverticesinV(G)andedgesetE(G).ThenumberofedgesofGisreconstructiblebecause(n−2)#E(G) is the total number of edges of all the cards of the deck.As well, the degree sequence of the graph G (this is the non-increasingsequenceofdegreesofalltheverticesofG)isreconstructiblesinceitequalsarearrangementofthe elementsoftheset {#E(G)−#E(C):C acardofthedeckofG}. Similarly,apropertyofagraphissaidtoberecognizableifonecandeterminewhetherthispropertyholdsforagraph GjustbylookingatthedeckofG. The same principle can be applied to algebraic invariants of the graph, that is, invariants of the quotient S of a polynomialringbytheedgeideal.Themaincontentofthispaperistoprovethatvariousalgebraicinvariantsofthe grapharereconstructible.Mostnotablywewillprovethatthemultiplicity,dimensionandHilbertfunctionofS,and thegradedBettinumbersofS innon-maximaldegreesarereconstructible. Justasthereconstructionconjecturehasproventobeextremelycomplicateddespiteitssimplestatement,wehave found that several of the reconstructible algebraic properties are either straightforward to verify, or seem to be very difficult.Forthisreason,wehaveincludedmanyquestionsandexamplesinthemanuscript,whichwehopewillinspire furtherinvestigationsonthisbeautifultopic. 2. Preliminaries We begin by reviewing some basic facts about edge ideals and Stanley–Reisner ideals.Villarreal’s book [10] is a comprehensiveintroductiontothesetopics. Definition2.1(Simplicialcomplexesandgraphs). Asimplicialcomplex(cid:3)overasetofverticesV=V((cid:3))={x1,...,xn} isacollectionofsubsetsofV,withthepropertythat{xi} ∈(cid:3) foralli,andifF ∈ (cid:3)thenallsubsetsofF (including theemptyset)arealsoin(cid:3).Anelementof(cid:3)iscalledafaceof(cid:3),andthedimensionofafaceF of(cid:3)isdefinedto be|F|−1,where |F|isthenumberofverticesofF.Thefacesofdimensions0and1arecalledverticesandedges, respectively,anddim∅=−1.Themaximalfacesof(cid:3)underinclusionarecalledfacetsof(cid:3).Thedimensionofthe simplicialcomplex(cid:3)isthemaximaldimensionofitsfacets. Thef-vectorof(cid:3)istheintegervector(f0,f1,...,fd),withfi thenumberoffacesofdimensioni in(cid:3). A(simple)graphGisasimplicialcomplexofdimension1.WedenotethesetofverticesandthesetofedgesofG byV(G)andE(G),respectively. Allgraphsthatweconsiderinthispaperaresimplegraphs. AvertexcoverforagraphGisasubsetAofV(G)thatintersectseveryedgeofG.IfA isaminimalelement(under inclusion)ofthesetofvertexcoversofG,itiscalledaminimalvertexcover.AgraphGisunmixedifallofitsminimal vertexcovershavethesamecardinality. Definition2.2(Stanley–Reisnerideal). Let(cid:3)beasimplicialcomplexovernverticesx1,...,xn.LetR=k[x1,...,xn] beapolynomialringoverafieldk.TheStanley–Reisneridealof(cid:3)istheidealI(cid:3) ofR generatedbythesquare-free monomialsxi1...xir,where{xi1,...,xir}isnotafaceof(cid:3).Similarly,ifI isasquare-freemonomialidealinRthen theuniquesimplicialcomplex(cid:3)onnverticeswithStanley–ReisneridealI istheStanley–ReisnercomplexofI. Definition2.3(Edgeideal). LetGbeagraphwithnverticesx1,...,xn.LetR=k[x1,...,xn]beapolynomialring overafieldk.TheedgeidealI(G)ofGistheidealofRgeneratedbythesquare-freemonomialsxixj,where{xi,xj} isanedgeofG. Clearly,agraphoveragivensetofverticesisuniquelydeterminedbyitsedgeideal.TheStanley–Reisnercomplex (cid:3)GofagraphGistheStanley–ReisnercomplexoftheedgeidealI(G). Definition2.4(Inducedsubgraph). GivenasubsetB ofverticesofagraphG,thesubgraphGB inducedbyB isthe graphwithvertexsetB andedges{{x,y}∈E(G) :x,y ∈B}. 2004 K.Dalilietal./DiscreteMathematics308(2008)2002–2010 Example2.5. LetI(G)=(xy,yz,zu,zv)betheedgeidealofthegraphG(picturedontheleft)intheringk[x,y,z,u,v]. TheStanley–ReisnercomplexofI(G)is(cid:3)G,picturedbelowontheright. y z x v y x u v z u Notethatthefacetsof(cid:3)G correspondtomaximalsubsetsofB ⊆ {x,y,z,u,v}wheretheinducedgraphGB has noedges(i.e.GB consistsofonlyisolatedvertices). 3. Theprimarydecomposition ForagraphGletGx betheinducedgraphonV(G)\{x}.Equivalently,thegraphGx isformedbyremovingavertex x (and its adjacent edges) from G.We call the collection of all such induced subgraphs the deck of G, denoted by D(G),andeachGx iscalledacardofthedeck.IfI(G)istheedgeidealofGinthepolynomialringR=k[x1,...,xn] and S =R/I(G), then the edge ideal of Gx is the image of I(G) under the quotient map R → Rx =R/(x). Let Sx =Rx/(I(G)Rx). Example3.1. LetGbethegraphgivenbelow: x u y z ThedeckD(G)consistsofthefollowingcards: b c c G: a b G: a x y b b c G: a G : a c z u Our goal, therefore, is to see what properties of the ideal I(G)=(xy,xz,xu,yz) we can recover from the edge idealsofthecards:I(Gx)=(ab),I(Gy)=(ab,bc),I(Gz)=(ab,bc),andI(Gu)=(ab,bc,ac). Wewillhaveoccasiontousethefollowingresultfromcombinatorialreconstructiontheory: Lemma3.2(Kelly’sLemma[6]). ForsimplegraphsFandGletS(F,G)denotethenumberofinducedsubgraphsof GthatareisomorphictoF.If#V(F)<#V(G),thenS(F,G)isareconstructibleinvariantofG. Proof. LabeltheverticesofG,andfixalabeledsubgraphisomorphictoF.Thenthissubgraphappearsasasubgraph of#V(G)−#V(F)cards.ThereareS(F,G)labeledsubgraphsisomorphictoF,so (cid:2) S(F,G)(#V(G)−#V(F))= S(F,Gx). x∈V(G) HenceS(F,G)isreconstructible. (cid:3) K.Dalilietal./DiscreteMathematics308(2008)2002–2010 2005 Lemma3.3(Minimal vertex cover of graph and deck). Suppose that G is a graph with deck D(G), and let x be a vertexofG.Then (1) IfAisaminimalvertexcoverofGcontainingx,A(cid:6)=A\{x}isaminimalvertexcoverforthecardGx. (2) IfA(cid:6)isaminimalvertexcoverofGx,theneitherA(cid:6)orA=A(cid:6)∪{x}isaminimalvertexcoverofG. Proof. (1)EveryedgeofGx isanedgeofGnotincidenttox.SinceAisavertexcoverofG,theseedgesmustbe incidenttoavertexinA,hencetoavertexinA(cid:6) =A\{x}.SoA(cid:6) isavertexcoverforGx.Moreover,A(cid:6) isminimal sinceifB(cid:6)(cid:2)A(cid:6) isaminimalvertexcoverofGx,thenB(cid:6)∪{x}(cid:2)AisasubcoverofA,contradictingtheminimalityof A. (2) Suppose that A(cid:6) is not a minimal vertex cover of G. Clearly A is a vertex cover of G. Suppose that there is a subset B(cid:2)A covering G.Then x ∈ B, since otherwise, B would be a proper subset of A(cid:6) covering Gx, which is a contradiction.SoB=B(cid:6)∪{x},withB(cid:6)(cid:2)A(cid:6).Bythepreviouspart,B(cid:6)isaminimalvertexcoverofGx,whichisagain acontradiction.SoAhastobeaminimalvertexcoverofG. (cid:3) Remark3.4. IfAisaminimalvertexcoverofGnotcontainingavertexx,Amayormaynotbeaminimalvertex coverforthecardGx.Forexample,takethegraphGwithI(G)=(xu,uy,yv).Then{y,x}isaminimalvertexcover ofbothGandGv,whereas{u,y}isaminimalvertexcoverofG,butnotofGv. WesummarizesomealgebraicfactsaboutI(G)inordertogiveanalgebraicinterpretationoftheminimalvertex covers.SincetheidealI(G)isradical,itistheintersectionoftheprimeidealscontainingit.Inparticular,I(G)isthe intersectionoftheprimescontainingI(G)thatareminimalwithrespecttoinclusion.Moreover,sinceI(G)isgenerated bymonomials,eachofitsminimalprimesisgeneratedbyasubsetofthevariables.Theideal (xi1,xi2,...,xik)has heightequaltothenumberofvariablesitcontains.TheKrulldimensionofS=k[x1,...,xn]/I(G)is dimS=n−(minimumheightofaminimalprimeofI(G)). (1) Itfollowsfromthedefinitionofaminimalvertexcoverthatthesetsofvariablesappearinginaminimalprimeof I(G)arepreciselytheminimalvertexcoversofG. ThefollowingisthealgebraictranslationofLemma3.3. Corollary3.5(Primarydecompositionofagraphanditsdeck). SupposethatGisagraphandI(G)itsedgeideal. (1) Ifp=(x1,...,xr)isaminimalprimeidealofheightr containingI(G),thentheideal(x1,...,xˆi,...,xr)isa minimalprimeidealcontainingI(Gxi).Inthiscase,thereareatleastr cardsinD(G)withaminimalprimeof heightr −1. (2) IfforsomevertexxofG,I(Gx)hasaminimalprimepofheightr−1,thenI(G)hasaminimalprimeofheight r −1(namelyp),oraminimalprimeofheightr (namelyp+(x)). SupposeH(G,r)denotesthenumberofheightrminimalprimesoftheidealI(G).ItfollowsdirectlyfromCorollary 3.5that Corollary3.6(Numberofcomponentsoffixedheight). LetGbeagraph.Thenforeachr (cid:2) 1 H(G,r)(cid:4) H(Gx,r −1). r x∈G Inparticular,ifd istheminimumpossibleheightforaprimeidealofI(G),then (cid:2) 1 H(G,d)= H(Gx,d−1). d x∈G 2006 K.Dalilietal./DiscreteMathematics308(2008)2002–2010 Proof. Part1justfollowsfrompart1ofCorollary3.5.Forpart2,weknowthataminimalprimepofheightd−1of acardGx couldonlycomefromaheightd minimalprimep+(x)ofI(G)(becausetherearenominimalprimesof I(G)ofheightd−1).SinceeachsuchminimalprimeofI(G)contributestoexactlyd cards,ourclaimfollows. (cid:3) 4. TheHilbertfunction The Hilbert function of a graded ring S =⊕n∈NSn, where S0 =k is a field, measures the growth of the graded components of S. To be precise, each graded piece Sn of S is a k-vector space and the Hilbert series of S is the generatingfunctionforthedimensionsofthesevectorspaces: (cid:2) HS(m)= dimkSnmn. n∈N TheHilbertfunctionofS isthefunctionH(S,m)=dimkSn. Asbefore,letGbeagraphandS=R/I(G).WewillshowthattheHilbertfunctionofS isreconstructible. Itiswellknown[2,Theorem5.1.7])thattheHilbertseriesofScanberepresentedintermsofthef-vector(f0,...,fd) oftheStanley–Reisnercomplex(cid:3)G: (cid:2)d f mi+1 i HS(m)= (1−m)i+1, i=−1 wheref−1=1isthenumberofemptysubgraphsinG.ItfollowsthattheHilbertfunctionofS canbedescribedas (cid:3) 1 (cid:5) (cid:6) ifm=0, H(S,m)= (cid:4)di=0fi m−i 1 ifm>0. (2) AsetAofverticesofagraphGiscalledindependentifnotwoelementsofAareconnectedbyanedgeinG.Let fs(G) be the number of independent sets of size s +1 inG, in other words (f0,f1,...,fd) is the f-vector of the Stanley–Reisnercomplex(cid:3)GofI(G). Lemma4.1. For a graph G with more than two vertices, the f-vector of the Stanley–Reisner complex of I(G) is reconstructible. Proof. LetKsbethecomplementofthecompletegraphKs,thatis,Ksisthegraphonsverticeswithnoedges.Notice thatfs(G)isthenumberofinstancesofthegraphKs inG.Ifs<n thisnumberisreconstructiblebyLemma3.2. Ifs=nthenumberiszerooronedependingonwhetherGistheemptygraphofnot,andsincetheemptygraphon morethantwoverticesisreconstructible,soisfs(G). (cid:3) SincetheHilbertfunctioncanbedescribedintermsofthef-vectorasdemonstratedin(2),weconcludethatthe Hilbertfunctionisreconstructible. Proposition4.2(Hilbert function is reconstructible). The Hilbert function of I(G) for a given graph G with more thantwoverticesisreconstructible. Asimmediatecorollariesoftheabovefacts,wecanshowthatthemultiplicityandKrulldimension(see(1))ofI(G) arealsoreconstructible. Corollary4.3(Dimension is reconstructible). For a graph G with more than two vertices, the (Krull) dimension of S=R/I(G)isreconstructible. Proof. TheKrulldimensionofS isequaltodim(cid:3)G +1([2,Theorem5.1.4]),whichwecanimmediatelycompute fromthef-vectorof(cid:3)GortheHilbertfunctionofS. (cid:3) K.Dalilietal./DiscreteMathematics308(2008)2002–2010 2007 ThemultiplicityofSisaninvariantthatcanbedescribedintermsofthecoefficientsofthenumeratoroftheHilbert function,andinthecasewearedealingwith,isthesameasfd,thenumberofd-dimensionalfacetsof(cid:3)G[2,Chapter 5]).Hence,thisvalueisalsoreconstructible,asthef-vector(ortheHilbertfunction)isreconstructible. Corollary4.4(Multiplicity is reconstructible). Given a graph G with more than two vertices, the multiplicity of S=R/I(G)isreconstructible. Remark4.5. The results of Section 3 provide a different proof for reconstruction of dimension and multiplicity. In particularonecandeducedimS=max{dimSx}. Remark4.6. Notice that Corollary 4.4 implies that we can reconstruct the number of components of Spec(S) of maximal dimension. This raises the question of whether the number of the components of a given non-maximal dimensionisalsoreconstructible.Inparticularitwouldbeofinteresttoknowwhetherunmixednessisrecognizable. Thatis,giventhedeckofagraphG,canwedeterminewhetheralltheminimalprimesofI(G)havethesameheight? 5. GradedBettinumbers Given a monomial ideal I in R =k[x1,...,xn], we define the multigraded Betti numbers (cid:2)i,b of I in terms of a multigradedminimalfreeresolutionofS=R/I asanR-module: 0←R/I ←R ←⊕bR(−b)(cid:2)1,b ←⊕bR(−b)(cid:2)2,b ←..., wherethemodulesR(−b)areshiftsofthep(cid:4)olynomialringRtomakethedifferentialsintheresolutionmultidegree- preservingmaps.Aswell,wedefine(cid:2)i,j = |b|=j(cid:2)i,b,where|b|=b1+···+bn.WhenI isasquarefreemonomial ideal(asisthecaseforI(G))theneachbappearingintheresolutionisalsosquarefreeinthesensethatb ∈ {0,1}n (see[2,Section5.5]). We will use Hochster’s formula from Stanley–Reisner theory to study the multigraded Betti numbers of the edge idealofagraph.WewillprovethatforagraphGonnverticesthegradedBettinumbers(cid:2)i,j arereconstructiblefor allj<n.ThereconstructionofthetopdegreeBettinumbers(cid:2)i,n,ontheotherhand,seemstobeverydifficult. SupposethatI =I(G)istheedgeidealofagraphG,andlet(cid:3)denotetheStanley–ReisnercomplexofI.Suppose b∈Zn isavectorconsistingof0’sand1’s,andletB={xi|bi =1}bethesupportofb.ThenbyHochster’sformula (see[2,Chapter5]),themultigradedBettinumber(cid:2)i,b ofR/I canbecomputedviathereducedsimplicialhomology ofcertainsubcomplexesof(cid:3): (cid:2)i,b=(cid:2)i,B :=dimkH(cid:7)|B|−i−1((cid:3)B;k), (3) where (cid:3)B denotes the restriction of (cid:3) to B; in other words, (cid:3)B ={F ∈ (cid:3)|F ⊆ B}.A simple unraveling of the definitionsshowsthat(cid:3)B isjusttheStanley–ReisnercomplexofI(GB). Theorem5.1(ReconstructionofgradedBettinumbers). LetGbeagraphonnvertices.ThenthegradedBettinumbers (cid:2)i,j ofI(G)arereconstructibleforallj<n. PStraonolfe.y–LReetiDsnebrecoamdpelcekxwofithI(cGar)d,sanladb(cid:3)elxedthGexS1t,a.n.l.e,yG–Rxne,isannedr cleotmGplebxeoafrGecxo,nfsotrruactvioenrteoxfxDo.fLGet.(cid:3)Sudpepnoosteeththaet B(cid:2)V ={x1,...,xn}.Ifx /∈B,thenremovingx andthenrestrictingtoB hasthesameeffectasjustrestrictingtoB: ((cid:3)x)B =(cid:3)B. ApplyingHochster’sformula(3),if(cid:2)xi,B denotesthemultigradedBettinumberofRx/I(Gx),andifx∈/B,then (cid:2)i,B =dimkH(cid:7)|B|−i−1((cid:3)B;k)=dimkH(cid:7)|B|−i−1((cid:3)xB;k)=(cid:2)xi,B. (cid:4) Since(cid:2)i,j = B⊆V,|B|=j(cid:2)i,B,wearedone. (cid:3) Remark5.2(ThetopdegreeBettinumber). CalculatingthedegreengradedBettinumber(cid:2)i,n,wherenisthenumber ofvariables,seemstobemuchmoredifficult.FromthefactthattheHilbertseriesisreconstructible,itfollowsthatthe 2008 K.Dalilietal./DiscreteMathematics308(2008)2002–2010 (cid:4) alternatingsum i(−1)i(cid:2)i,nisreconstructible.Inlightofthis,itwouldbehelpfulifweknewthatthetopdegreeBetti numbersoccurredonlyinonespotoftheresolution.However,thisisnotalwaystrue.Theexamplebelowillustrates thisfact;similarexamplescanbeconstructedwiththetopBettinumbersindifferentcolumnsoftheBettidiagram. InthecasewhereweknowthatI(G)isaCohen–Macaulayideal,though,thetopdegreeBettinumbercanappear only at the last slot of the resolution [10, Proposition 4.2.3]. Therefore in this case all graded Betti numbers are reconstructible.WewouldliketothankHosseinSabzrouforpointingthisouttous. Example5.3. LetR=k[x ,...,x ],and 1 9 I =(x x ,x x ,x x ,x x ,x x ,x x ,x x ,x x ,x x ,x x ,x x ,x x ). 1 2 3 4 5 6 7 8 9 1 9 2 9 3 9 4 9 5 9 6 9 7 9 8 Macaulay2[3]returnsthefollowingBettidiagramforR/I. total: 1 12 38 66 75 57 28 8 1 0: 1 . . . . . . . . 1: . 12 32 56 70 56 28 8 1 2: . . 6 6 . . . . . 3: . . . 4 4 . . . . 4: . . . . 1 1 . . . Toreadthisdiagram,assumethattherowsandcolumnsarenumbered0,1,2,... .Thentheentryintheithrowand jthcolumnistheBettinumber(cid:2)j,i+j. We see in the diagram that (cid:2)5,9 =(cid:2)8,9 =1, so the degree 9 Betti number happens in two different spots of the resolution. NotethatthehighestdegreegradedBettinumbercontrolsmanyotherinvariantsofI(G). Proposition5.4. LetGbeagraphonnvertices.Ifthegradedtop-degreeBettinumbers(cid:2)i,nofI(G)arereconstructible, thenthealgebraicinvariantsdepth,projectivedimensionandregularityofI(G)arereconstructible. Proof. We already know from Theorem 5.1 that all other graded Betti numbers are reconstructible. The projective dimensionof I(G)isthemaximum i suchthat (cid:2)i,j (cid:10)= 0,andsoonceweknowalltheBettinumbers,weknowthe projectivedimension.OnecanthenapplytheAuslander–Buchsbaumformula(see[2,Chapter1])tocomputethedepth from the projective dimension.The regularity of I(G) is defined as the maximum value of j −i where the graded Bettinumber(cid:2)i,j (cid:10)=0.Soonceagain,reconstructingalltheBettinumberswillleadtoreconstructingtheregularityof I(G). (cid:3) Anaturalquestionis:Cantheseinvariantsbereconstructedindependentofthereconstructionofthetop-degreeBetti numbers? ThefollowingexampleshowsthatwecannothopetohaveuniquenessofidealsassociatedtoBettidiagrams,even iftheidealsareedgeideals. Example5.5. Considerthefollowingtwographs. TheiredgeidealshavethesameBettidiagram,eventhoughthegraphsaredifferent. total: 1 4 4 1 0: 1 . . . 1: . 4 4 1 K.Dalilietal./DiscreteMathematics308(2008)2002–2010 2009 In[5]KatzmanconstructedagraphGforwhichtheBettidiagramofGdependsonthecharacteristicoftheground field.IfH isasmallestsuchgraph,thentheBettidiagramsofH\{v}areallcharacteristicindependent,whiletheBetti diagramofH itselfdependsonthecharacteristicofthegroundfield.ThereforetheknowledgeoftheBettidiagramsof thecardsinthedeckofagraphisnotsufficienttoreconstructtheBettinumbersofthegraph.Howeveriftheground fieldisknownthisbecomesaninterestingquestion: Question5.6. SupposethatthefieldkandtheBettidiagramsofallthecardsinthedeckofGaregiven.CantheBetti diagramofGbereconstructedfromthisinformation? 6. Suspendedgraphs Suspendedgraphs(see[9,10])provideanimportantsetofexamplesofCohen–Macaulaygraphs.Itisknownthata treeisCohen–Macaulayifandonlyifitissuspended(ifandonlyifitisunmixed;see[9]). Definition6.1(Suspension). LetGbeagraphonnvertices{x1,...,xn}.ThesuspensionofGisthegraphobtained byattachingtoeachvertexxithenewvertexyiandtheedge{xi,yi}.WecallagraphGsuspendedifitisthesuspension ofanothergraph. Example6.2. ThegraphbelowisthesuspensionofthegraphGwithI(G)=(x x ,x x ). 1 2 1 3 y 1 y 3 x1 y2 x 3 x 2 MotivatedbythegoalofinvestigatingthereconstructibilityoftheCohen–Macaulaygraphsweprovethatsuspended graphsarerecognizableandreconstructible. Lemma6.3. SupposethatGisaconnectedgraphwith2n>2 vertices.Thenumberofcardswithexactlyoneisolated vertexinthedeckofGisequaltonifandonlyifGissuspended. Proof. IfGissuspendedthenthecardsinthedeckcorrespondingtoremovalofdegreeoneverticesareconnected. Andthecardsinthedeckcorrespondingtheremovalofanyoftheotherverticeshaveexactlyoneisolatedvertex,i.e. thedegreeonevertexsuspendingtheremovedvertex. Conversely suppose there are n cards in the deck of a connected graph G, each with exactly one isolated vertex. Thesecardscorrespondtoremovalofnverticesx1,x2,...,xn.Weclaimeachoneofthexi’shasexactlyoneneighbor withdegreeone,andnoneofthexi’shavedegreeone.Thefirstpartoftheclaimfollowsfromthefactthatremoving xi producesacardwithexactlyoneisolatedvertex,andthesecondpartfromthefactthatGisconnected.Sothe2n verticesofGarepartitionedintotwosets,thexi’sandtheirdegreeoneneighbors.SoGissuspended. (cid:3) Asacorollarywegetthatsuspendedgraphsarerecognizable. Corollary6.4. Suspendedgraphsarerecognizable. Proof. OurgoalistoprovethatgiventhedeckofagraphG,itispossibletodecidewhetherGissuspendedornot. Sincedisconnectedgraphsarerecognizableandreconstructible,ifthedeckisthedeckofadisconnectedgraphthen byreconstructingthegraphwecandecidewhetheritissuspendedornot.Ifthedeckisthedeckofaconnectedgraph thenusingthepreviouslemmawecandecidewhetherornotitissuspended. (cid:3) Theorem6.5(Reconstructionofsuspendedgraphs). Suspendedgraphswithmorethantwoverticesarereconstructible. 2010 K.Dalilietal./DiscreteMathematics308(2008)2002–2010 Proof. Sincewehaveprovedthatsuspendedgraphsarerecognizable,andsincedisconnectedgraphsarereconstructible wemayassumewehaveadeckknowntobelongtoaconnectedsuspendedgraphGandattempttoreconstructG.To dothiswefirstreconstructthedegreesequenceofG.Weconsidertwoseparatecases: Case 1. The highest degree in the degree sequence of G is 2. Suppose G is a suspension of a graph G(cid:6). By our assumption, every vertex ofG(cid:6) is of degree 1, and sinceG(cid:6) is connected, it can only be the graph consisting of one edge.SointhiscaseGisjustapathoflength3. Case2.Thehighestdegreeisd>2.Letd1=d,d2,...,d2n−1,d2n=1bethedegreesequenceofG.Alsoletvbea vertexofdegreed andletwbeitsdegreeoneneighbor.Removingwwillproduceacardwhosedegreesequenceisa rearrangementofthesequenced1−1,d2,d3,...,d2n−1innon-increasingorder.Pickacardwiththisdegreesequence. Amongallverticesofdegreed −1inthiscardexactlyonedoesnothaveadegreeoneneighbor,thatvertexisv and addinganewvertexofdegreeoneconnectedtovwillresultinagraphisomorphictoG. (cid:3) IfGisasuspendedgraphthenR/I(G)isCohen–Macaulay.SoaclassofCohen–Macaulaygraphsisreconstructible. Anaturalquestionis:AreallCohen–Macaulaygraphsreconstructible? Anothernaturalanddifficultquestionis:Whichreconstructiblealgebraicparameterswouldimplythereconstruction conjecture? References [1]J.A.Bondy,Agraphreconstructor’smanual,Surveysincombinatorics,1991(Guildford,1991),LondonMathematicalSocietyLectureNote Series,166,CambridgeUniversityPress,Cambridge,1991,pp.221–252. [2]W.Bruns,J.Herzog,Cohen-Macaulayrings,(revisededition)vol.39,CambridgeStudiesinAdvancedMathematics,1998. [3]D.R. Grayson, M.E. Stillman, Macaulay 2, a software system for research in algebraic geometry, available at (cid:11)http://www.math. uiuc.edu/Macaulay2/(cid:12). [4]H.T.Hà,A.VanTuyl,Splittableidealsandtheresolutionsofmonomialideals,J.Algebra309(2007)405–425. [5]M.Katzman,Characteristic-independenceofBettinumbersofgraphideals,J.Combin.TheorySer.A113(2006)435–454. [6]P.J.Kelly,Acongruencetheoremfortrees,PacificJ.Math.7(1957)961–968. [7]M.Roth,A.VanTuyl,Onthelinearstrandofanedgeideal,preprint(2006). [8]A.Simis,W.Vasconcelos,R.Villarreal,Ontheidealtheoryofgraphs,J.Algebra167(2)(1994)389–416. [9]R.Villarreal,Cohen–Macaulaygraphs,ManuscriptaMath.66(3)(1990)277–293. [10]R.Villarreal,Monomialalgebras,MonographsandTextbooksinPureandAppliedMathematics,vol.238,MarcelDekkerInc.,NewYork,2001.