ORTHOGONAL POLYNOMIALS AND COMBINATORICS

ORTHOGONALPOLYNOMIALSANDCOMBINATORICSD.StantonJune26,2000Abstract.Anintroductionisgiventotheuseorthogonalpolynomialsindistanceregulargraphsandenumeration.Someexamplesineachareaaregiven,alongwithopenproblems.1.Introduction.Therearemanywaysthatorthogonalpolynomialscanoccurincombinatorics.Thispaperconcentratesontwotopics(1)eigenvaluesofdistanceregulargraphs,(2)generatingfunctionsforcombinatorialobjects.Theintroductiontothesetwotopicsiswell-knowntotheexperts,andisintendedforageneralaudience.Ratherthangiveanexhaustivesurvey,specicapplicationswhichhighlightthetechniquesofeachsubjectaregiven.For(1),theapplicationisWilson’sproofoftheErdos-Ko-Radotheorem(seex3).For(2),twoapplicationswillbegiven-Foata’sproofoftheMehlerformulaforHermitepolynomialsandtheKim-ZenglinearizationtheoremforSheerorthogonalpolynomials.Someopenproblemsaregivenalongtheway.Activeresearchtopicswhicharenotdiscussedincludegroupandalgebrarepre-sentations,tableauxandsymmetricfunctions.Thestandardreferencesfordistanceregulargraphsandassociationschemesare[5]and[9],while[25]coverstopics(1)and(2).Thestandardnotationforhypergeometricseriesfoundin[22]isusedhere.2.Associationschemesanddistanceregulargraphs.InclassicalcodingtheorytheKrawtchoukpolynomialsareimportantforseveralproblems.ThiswasgeneralizedtopolynomialsinP-polynomialassociationschemesbyDelsarte[13],andinthissectionwereviewthisbasicsetup.RecallthatagraphG=(V;E)consistsofasetVofvertices,andasetEofunorderedpairsofelementsofV,calledtheedgesofG.IfthegraphGisveryregularinaprecisesensethenassociatedtoGisanitesequenceoforthogonalpolynomials.TheadjacencymatrixAofthegraphGisthejVjjVjmatrixdenedby(therowsandcolumnsareindexedbytheverticesofG)A(x;y)=1ifxyisanedge,0otherwise.ResearchpartiallysupportedbyNSFgrantDMS99-7062712D.STANTONWeimaginetheadjacencymatrixaskeepingtrackofwhichpairsofverticesaredistanceonefromeachother,wherethedistancebetweentwoverticesisthelengthoftheshortestpathinthegraphconnectingthem.Thisdistanceisniteaslongasthegraphisconnected.Theadjacencymatrixcanbegeneralizedtodistancei,Ai(x;y)=1ifd(x;y)=i,0otherwise.WeseethatA0=I,A1=A,andifthegraphisconnectedwithmaximumdistanced,thenA0+A1++Ad=J,theallonesmatrix.WewantaconditiononthegraphGwhichmimicsthethree-termrecurrencerelationxpi(x)=ipi+1(x)+ip(x)+ipi1(x)whichissatisedbyanysetoforthogonalpolynomials.Supposethatx;y2V,withd(x;y)=i.Ifonemovesdistanceoneawayfromytoavertexz,thenwehaved(x;z)=i1;iori+1.TheconditionweimposeontheconnectedgraphGwithmaximumdistancedisdistanceregularity,namelythematricesAifollowthesamerule:(2.1)AiA1=ci+1Ai+1+aiAi+bi1Ai1;0id;forsomeconstantsci+1,aiandbi1.Ifsuchconstantsexist,thentheycanbefoundbyexplicitcounting.Forexample,ifwexx;z2V,withd(x;z)=i+1,ci+1isthenumberofy2Vsuchthatd(x;y)=i;d(y;z)=1.Sinceci+1isindependentofthechoiceofx;zwithd(x;z)=i+1,thegraphGmustberegularinaveryspecialway,thusthetermdistanceregular.Wenowgivetwoexamplesofdistanceregulargraphs.TherstistheN-dimensionalcube,whichisdenotedH(N;2),andisreferredtoasthebinaryHam-mingscheme.TheverticesofH(N;2)areallN-tuplesof0’sand1’s,andanedgeconnectstwoN-tupleswhichdierinexactlyoneposition.Thedistancebetweentwoverticesisthenumberofpositionsinwhichtheydier.Inthiscaseci+1=i+1;ai=0;bi1=Ni+1:Forexampletocomputeci+1,xx=(0;0;;0),andz=(1;;1;0;;0)wherezhasi+11’ssothatd(x;z)=i+1.Ifd(y;z)=1andd(x;y)=i,thenymustbeobtainedbyswitchingoneofthe1’sinztoa0,therearei+1choicesforthisswitch.Thesecondexample,J(n;k),theJohnsonscheme,willbeconsideredindetailinthenextsection.TheverticesVofJ(n;k)consistofallk-elementsubsetsofthexedn-elementsetf1;2;;ng=[n],andtwosubsets;2Vareconnectedbyedgeifj\j=k1.Inthiscasethedistanceisgivenbyd(;)=kj\j,andtheconstantsareci+1=(i+1)2;ai=i(nki)+(ki)i;bi1=(ki+1)(ni+1):Thistimetoseethatci+1=(i+1)2,xk-subsetsxandzwithjx\zj=k(i+1).Wemustcounthowmanyyaredistanceonefromzanddistanceifromx.ToORTHOGONALPOLYNOMIALSANDCOMBINATORICS3createy,wejustdeleteapointofzfromzx,andaddapointtozfromxz.Thiscanbedonein(i+1)2ways.NotealsothatjVj=nk.Thesetwoexampleshavelargesymmetrygroups-permutationsoftheverticeswhichpreservethedistanceinthegraph-whichensuredistanceregularity.Itisclearfrom(2.1)thatAi=pi(A1)isapolynomialofdegreeiinA1,wherepi(x)isanorthogonalpolynomial,aslongasci+16=0fori+1d.Thisisthecaseifthegraphisconnected.ByconsideringtheeigenvaluesofA1wewillhavearealvaluedpolynomialinsteadofamatrixvaluedpolynomialpi(A1).ThematrixA1isarealsymmetricmatrix,soA1hasacompletesetofrealeigenvalues.Infactthereared+1distincteigenvalues,01d,withcorrespondingeigenspacesV0;V1;;Vd.SinceAiisapolynomialinA1,theeigenvalueofAionVjispi(j).Notethatthed+1eigenvaluesaresolutionstothed+1degreepolynomialequation(thei=dcaseof(2.1))pd()=adpd()+bd1pd1():Adiscreteorthogonalityrelationcanbefoundusingtheeigenspaces.LetEjbetheprojectionmapontotheeigenspaceVj.ThenwehaveAi=dXj=0pi(j)Ej:Ifthisrelationisinverted,andtheorthogonalityoftheprojectionmapsEjisused,thefollowingorthogonalityrelationsareobtained.Weletvidenotethesizeofasphereofradiu