DMTCS Proceedings, 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010)

Font Size:  Small  Medium  Large

On γ-vectors satisfying the Kruskal-Katona inequalities

E. Nevo, T. K. Petersen

Abstract


We present examples of flag homology spheres whose γ-vectors satisfy the Kruskal-Katona inequalities. This includes several families of well-studied simplicial complexes, including Coxeter complexes and the simplicial complexes dual to the associahedron and to the cyclohedron. In these cases, we construct explicit flag simplicial complexes whose f-vectors are the γ-vectors in question, and so a result of Frohmader shows that the γ-vectors satisfy not only the Kruskal-Katona inequalities but also the stronger Frankl-Füredi-Kalai inequalities. In another direction, we show that if a flag (d-1)-sphere has at most 2d+3 vertices its γ-vector satisfies the Frankl-Füredi-Kalai inequalities. We conjecture that if Δ is a flag homology sphere then γ(Δ) satisfies the Kruskal-Katona, and further, the Frankl-Füredi-Kalai inequalities. This conjecture is a significant refinement of Gal's conjecture, which asserts that such γ-vectors are nonnegative.
Résumé. Nous présentons des exemples de sphères d'homologie flag dont γ-vecteurs satisfaire les inégalités de Kruskal-Katona. Cela comprend plusieurs familles de bien étudiés simplicial complexes, y compris les complexes de Coxeter et les complexes simpliciaux dual de l'associahedron et à la cyclohedron. Dans ces cas, nous construisons explicite flag simplicial complexes dont f-vecteurs sont les γ-vecteurs en question, et ainsi de suite de Frohmader montre que le γ-vecteurs de satisfaire non seulement les inégalités de Kruskal-Katona mais aussi la plus fortes inégalités Frankl-Füredi-Kalai. Dans une autre direction, nous montrons que, si un flag (d-1)-sphère a au plus 2d+3 ses sommets γ-vecteur satisfait aux inégalités de Frankl-Füredi-Kalai. Nous conjecture que, si Δ est une sphère d'homologie flag alors γ(Δ) satisfait aux inégalités de Kruskal-Katona, en outre, les de Frankl-Füredi-Kalai. Cette conjecture est un raffinement significative de la conjecture de Gal, qui affirme que ces γ-vecteurs sont nonnégatifs.

Full Text: PostScript PDF

Valid XHTML 1.0 Transitional