Hilbert Polynomials in Combinatorics
Francesco Brenti
DOI: 10.1023/A:1008656320759
Abstract
We prove that several polynomials naturally arising in combinatorics are Hilbert polynomials of standard graded commutative k-algebras.
Pages: 127–156
Keywords: standard graded algebra; Hilbert polynomial; Hilbert function; chromatic polynomial; Coxeter system
Full Text: PDF
References
1. D. Alvis, “The left cells of the Coxeter group of type H4,” J. Algebra 107 (1987), 160-168.
2. I. Anderson, Combinatorics of Finite Sets, Oxford Science Publications, Clarendon Press, Oxford, 1987.
3. M.F. Atiyah and I.G. Macdonald, Introduction to Commutative Algebra, Addison-Wesley, Reading, MA, 1969.
4. D. Bayer, “Chromatic polynomials and Hilbert functions,” preprint.
5. A. Bj\ddot orner, “Some combinatorial and algebraic properties of Coxeter complexes and Tits buildings,” Adv. in Math. 52 (1984), 173-212.
6. A. Bj\ddot orner, “Face numbers of complexes and polytopes,” Proceedings of the Int. Congress of Mathematicians, Berkeley, California, U.S.A., 1986, pp. 1408-1418.
7. A. Bj\ddot orner, A. Garsia, and R. Stanley, “An introduction to Cohen-Macaulay partially ordered sets,” in Ordered Sets, I. Rival (Ed.), Reidel, Dordrecht/Boston, 1982, pp. 583-615.
8. F. Brenti, Unimodal, log-concave, and Pólya Frequency sequences in Combinatorics, Memoirs Amer. Math. Soc., No. 413, 1989.
9. F. Brenti, “Expansions of chromatic polynomials and log-concavity,” Trans. Amer. Math. Soc. 332 (1992), 729-756.
10. F. Brenti, G. Royle, and D. Wagner, “Location of zeros of chromatic and related polynomials of graphs,” Canadian J. Math. 46 (1994), 55-80.
11. F. Brenti, “q-Eulerian polynomials arising from Coxeter groups,” Europ. J. Combinatorics 15 (1994), 417- 441.
12. W. Bruns and J. Herzog, Cohen-Macaulay Rings, Cambridge Studies in Advanced Mathematics, No. 39, Cambridge Univ. Press, Cambridge, 1993.
13. G. Clements and B. Lindstr\ddot om, “A generalization of a combinatorial theorem of Macaulay,” J. Combinatorial Theory 7 (1969), 230-238.
14. L. Comtet, Advanced Combinatorics, Reidel, Dordrecht/Boston, 1974.
15. V.V. Deodhar, “On some geometric aspects of Bruhat orderings. I. A finer decomposition of Bruhat cells,” Invent. Math. 79 (1985), 499-511.
16. P. Edelman, “Chain enumeration and non-crossing partitions,” Discrete Math. 31 (1980), 171-180.
17. D. Foata and M. Schutzenberger, Theorie geometrique des polynomes euleriens, Lecture Notes in Mathematics, No. 138, Springer-Verlag, Berlin, New York, 1970.
18. I. Gessel, “A note on Stirling permutations,” preprint.
19. I. Gessel and R. Stanley, “Stirling polynomials,” J. Combinatorial Theory (A) 24 (1978), 24-33. P1: KCU Journal of Algebraic Combinatorics KL540-Brenti January 21, 1998 12:5 156 BRENTI
20. R. Hartshorne, “Connectedness of the Hilbert scheme,” Publ. Math. de l'I.H.E.S., No. 29 (1966), 5-48.
21. J.E. Humphreys, Reflection Groups and Coxeter Groups, Cambridge Studies in Advanced Mathematics, No. 29, Cambridge Univ. Press, Cambridge, 1990.
22. D. Kazhdan and G. Lusztig, “Representations of Coxeter groups and Hecke algebras,” Invent. Math. 53 (1979), 165-184.
23. D. Kazhdan and G. Lusztig, “Schubert varieties and Poincaré duality,” in Geometry of the Laplace Operator, Proc. Sympos. Pure Math., Amer. Math. Soc., Providence, RI, 1980, Vol. 34, pp. 185-203.
24. F.S. Macaulay, “Some properties of enumeration in the theory of modular systems,” Proc. London Math. Soc. 1927, Vol. 26, pp. 531-555.
25. I.G. Macdonald, Symmetric Functions and Hall Polynomials, Oxford University Press, New York/London, 1979.
26. R.C. Read, “An introduction to chromatic polynomials,” J. Combinatorial Theory 4 (1968), 52-71.
27. R.C. Read and W.T. Tutte, “Chromatic polynomials,” in Selected Topics in Graph Theory 3, Beineke and Wilson (Eds.), Academic Press, New York, 1988.
28. L. Roberts, “Hilbert polynomials and minimum Hilbert functions,” in Queen's Papers in Pure and Applied Mathematics, No. 61 (The Curves Seminar at Queen's, Vol. II), A.V. Geramita (Ed.), Queen's University, Kingston, Ontario, 1982.
29. R. Stanley, Ordered Structures and Partitions, Memoirs Amer. Math. Soc., No. 119, 1972.
30. R. Stanley, “Hilbert functions of graded algebras,” Adv. in Math. 28 (1978), 57-83.
31. R.P. Stanley, Combinatorics and Commutative Algebra, Birkh\ddot auser, 1983.
32. R. Stanley, “An Introduction to combinatorial commutative algebra,” in Enumeration and Design, D.M. Jackson and S.A. Vanstone (Eds.), Academic Press, Toronto, 1984, pp. 3-18.
33. R.P. Stanley, Enumerative Combinatorics, Vol. 1, Wadsworth and Brooks/Cole, Monterey, CA, 1986.
34. R.P. Stanley, Private communication, 1987.
2. I. Anderson, Combinatorics of Finite Sets, Oxford Science Publications, Clarendon Press, Oxford, 1987.
3. M.F. Atiyah and I.G. Macdonald, Introduction to Commutative Algebra, Addison-Wesley, Reading, MA, 1969.
4. D. Bayer, “Chromatic polynomials and Hilbert functions,” preprint.
5. A. Bj\ddot orner, “Some combinatorial and algebraic properties of Coxeter complexes and Tits buildings,” Adv. in Math. 52 (1984), 173-212.
6. A. Bj\ddot orner, “Face numbers of complexes and polytopes,” Proceedings of the Int. Congress of Mathematicians, Berkeley, California, U.S.A., 1986, pp. 1408-1418.
7. A. Bj\ddot orner, A. Garsia, and R. Stanley, “An introduction to Cohen-Macaulay partially ordered sets,” in Ordered Sets, I. Rival (Ed.), Reidel, Dordrecht/Boston, 1982, pp. 583-615.
8. F. Brenti, Unimodal, log-concave, and Pólya Frequency sequences in Combinatorics, Memoirs Amer. Math. Soc., No. 413, 1989.
9. F. Brenti, “Expansions of chromatic polynomials and log-concavity,” Trans. Amer. Math. Soc. 332 (1992), 729-756.
10. F. Brenti, G. Royle, and D. Wagner, “Location of zeros of chromatic and related polynomials of graphs,” Canadian J. Math. 46 (1994), 55-80.
11. F. Brenti, “q-Eulerian polynomials arising from Coxeter groups,” Europ. J. Combinatorics 15 (1994), 417- 441.
12. W. Bruns and J. Herzog, Cohen-Macaulay Rings, Cambridge Studies in Advanced Mathematics, No. 39, Cambridge Univ. Press, Cambridge, 1993.
13. G. Clements and B. Lindstr\ddot om, “A generalization of a combinatorial theorem of Macaulay,” J. Combinatorial Theory 7 (1969), 230-238.
14. L. Comtet, Advanced Combinatorics, Reidel, Dordrecht/Boston, 1974.
15. V.V. Deodhar, “On some geometric aspects of Bruhat orderings. I. A finer decomposition of Bruhat cells,” Invent. Math. 79 (1985), 499-511.
16. P. Edelman, “Chain enumeration and non-crossing partitions,” Discrete Math. 31 (1980), 171-180.
17. D. Foata and M. Schutzenberger, Theorie geometrique des polynomes euleriens, Lecture Notes in Mathematics, No. 138, Springer-Verlag, Berlin, New York, 1970.
18. I. Gessel, “A note on Stirling permutations,” preprint.
19. I. Gessel and R. Stanley, “Stirling polynomials,” J. Combinatorial Theory (A) 24 (1978), 24-33. P1: KCU Journal of Algebraic Combinatorics KL540-Brenti January 21, 1998 12:5 156 BRENTI
20. R. Hartshorne, “Connectedness of the Hilbert scheme,” Publ. Math. de l'I.H.E.S., No. 29 (1966), 5-48.
21. J.E. Humphreys, Reflection Groups and Coxeter Groups, Cambridge Studies in Advanced Mathematics, No. 29, Cambridge Univ. Press, Cambridge, 1990.
22. D. Kazhdan and G. Lusztig, “Representations of Coxeter groups and Hecke algebras,” Invent. Math. 53 (1979), 165-184.
23. D. Kazhdan and G. Lusztig, “Schubert varieties and Poincaré duality,” in Geometry of the Laplace Operator, Proc. Sympos. Pure Math., Amer. Math. Soc., Providence, RI, 1980, Vol. 34, pp. 185-203.
24. F.S. Macaulay, “Some properties of enumeration in the theory of modular systems,” Proc. London Math. Soc. 1927, Vol. 26, pp. 531-555.
25. I.G. Macdonald, Symmetric Functions and Hall Polynomials, Oxford University Press, New York/London, 1979.
26. R.C. Read, “An introduction to chromatic polynomials,” J. Combinatorial Theory 4 (1968), 52-71.
27. R.C. Read and W.T. Tutte, “Chromatic polynomials,” in Selected Topics in Graph Theory 3, Beineke and Wilson (Eds.), Academic Press, New York, 1988.
28. L. Roberts, “Hilbert polynomials and minimum Hilbert functions,” in Queen's Papers in Pure and Applied Mathematics, No. 61 (The Curves Seminar at Queen's, Vol. II), A.V. Geramita (Ed.), Queen's University, Kingston, Ontario, 1982.
29. R. Stanley, Ordered Structures and Partitions, Memoirs Amer. Math. Soc., No. 119, 1972.
30. R. Stanley, “Hilbert functions of graded algebras,” Adv. in Math. 28 (1978), 57-83.
31. R.P. Stanley, Combinatorics and Commutative Algebra, Birkh\ddot auser, 1983.
32. R. Stanley, “An Introduction to combinatorial commutative algebra,” in Enumeration and Design, D.M. Jackson and S.A. Vanstone (Eds.), Academic Press, Toronto, 1984, pp. 3-18.
33. R.P. Stanley, Enumerative Combinatorics, Vol. 1, Wadsworth and Brooks/Cole, Monterey, CA, 1986.
34. R.P. Stanley, Private communication, 1987.