资源描述:
《AN ELEMENTARY CHROMATIC REDUCTION FOR GAIN GRAPHS AND SPECIAL HYPERPLANE ARRANGEMENTS》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、ANELEMENTARYCHROMATICREDUCTIONFORGAINGRAPHSANDSPECIALHYPERPLANEARRANGEMENTSPASCALBERTHOME,RAULCORDOVIL,DAVIDFORGE,´VERONIQUEVENTOS,ANDTHOMASZASLAVSKY´Abstract.Againgraphisagraphwhoseedgesarelabelledinvertiblybygainsfromagroup.Aweakchromaticfunctionofgaingraphswithgainsinafixedgroupsatisfiestwolaws
2、:deletion-contractionforlinkswithneutralgain,andnullityongraphswithaneutralloop.Thelawsareanalogoustothoseofthechromaticpolynomialofanordinarygraph,thoughtheyaredifferentfromthoseusuallyassumedofgaingraphsormatroids.Thetwolawsleadtotheweakchromaticgroupofgaingraphs,whichistheuniversaldomainforwea
3、kchromaticfunctions.Wefindexpressions,validinthatgroup,foragaingraphintermsofminorswithoutneutral-gainedges,orwithaddedcompleteneutral-gainsubgraphs,thatgeneralizetheexpressionofanordinarychromaticpolynomialintermsofmonomialsorfallingfactorials.Theseexpressionsimplyrelationsforallfunctionsofgaing
4、raphs,suchaschromaticpolynomials,thatsatisfythedeletion-contractionidentityforneutrallinksandarezeroongraphswithneutralloops.Examplesarethetotalchromaticpolynomialofanygaingraph,includingitsspecializationthezero-freechromaticpolynomial,andtheintegralandmodularchromaticfunctionsofanintegralgaingr
5、aph.Weapplyourrelationstosomespecialintegralgaingraphsincludingthosethatcorre-spondtotheShi,Linial,andCatalanarrangements,therebyobtainingnewevaluationsornewproofsofthezero-freechromaticpolynomialandtheintegralandmodularchromaticfunctionsofthesegaingraphs,hencethecharacteristicpolynomialsandhype
6、rcubicallattice-pointcountingfunctionsofthearrangements.TheproofinvolvesgaingraphsbetweentheCatalanandShigraphswhosepolynomialsareexpressedintermsofdescendingpathcoversofthegraphof(−1)-gainedges.WealsoshowhowtocalculatethetotalchromaticpolynomialofanygaingraphandespeciallyoftheCatalan,Shi,andLin
7、ialgaingraphs.1.IntroductionTocalculatethechromaticpolynomialχΓ(q)ofasimplegraphthereisastandardmethodthatcomesintwoforms.Onecandeleteandcontractedges,repeatedlyapplyingtheidentityχΓ=χΓe−χΓ/eandthereductionχΓ(q)=0ifΓhasaloo