Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs

Huh, June

doi:10.1090/S0894-0347-2012-00731-0

Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs
HTML articles powered by AMS MathViewer

by June Huh

J. Amer. Math. Soc. 25 (2012), 907-927

DOI: https://doi.org/10.1090/S0894-0347-2012-00731-0

Published electronically: February 8, 2012

PDF | Request permission

Abstract:

The chromatic polynomial $\chi _G(q)$ of a graph $G$ counts the number of proper colorings of $G$. We give an affirmative answer to the conjecture of Read and Rota-Heron-Welsh that the absolute values of the coefficients of the chromatic polynomial form a log-concave sequence. The proof is obtained by identifying $\chi _G(q)$ with a sequence of numerical invariants of a projective hypersurface analogous to the Milnor number of a local analytic hypersurface. As a by-product of our approach, we obtain an analogue of Kouchnirenko’s theorem relating the Milnor number with the Newton polytope; we also characterize homology classes of $\mathbb {P}^n \times \mathbb {P}^m$ corresponding to subvarieties and answer a question posed by Trung-Verma.

References

Martin Aigner, Whitney numbers, Combinatorial geometries, Encyclopedia Math. Appl., vol. 29, Cambridge Univ. Press, Cambridge, 1987, pp. 139–160. MR 921072
Paolo Aluffi, Computing characteristic classes of projective schemes, J. Symbolic Comput. 35 (2003), no. 1, 3–19. MR 1956868, DOI 10.1016/S0747-7171(02)00089-5
Francesco Brenti, Log-concave and unimodal sequences in algebra, combinatorics, and geometry: an update, Jerusalem combinatorics ’93, Contemp. Math., vol. 178, Amer. Math. Soc., Providence, RI, 1994, pp. 71–89. MR 1310575, DOI 10.1090/conm/178/01893
Winfried Bruns and Jürgen Herzog, Cohen-Macaulay rings, Cambridge Studies in Advanced Mathematics, vol. 39, Cambridge University Press, Cambridge, 1993. MR 1251956
David A. Cox, John Little, and Donal O’Shea, Using algebraic geometry, 2nd ed., Graduate Texts in Mathematics, vol. 185, Springer, New York, 2005. MR 2122859
Alexandru Dimca, Singularities and topology of hypersurfaces, Universitext, Springer-Verlag, New York, 1992. MR 1194180, DOI 10.1007/978-1-4612-4404-2
Alexandru Dimca and Stefan Papadima, Hypersurface complements, Milnor fibers and higher homotopy groups of arrangments, Ann. of Math. (2) 158 (2003), no. 2, 473–507. MR 2018927, DOI 10.4007/annals.2003.158.473
William Fulton, Introduction to toric varieties, Annals of Mathematics Studies, vol. 131, Princeton University Press, Princeton, NJ, 1993. The William H. Roever Lectures in Geometry. MR 1234037, DOI 10.1515/9781400882526
Terence Gaffney, Integral closure of modules and Whitney equisingularity, Invent. Math. 107 (1992), no. 2, 301–322. MR 1144426, DOI 10.1007/BF01231892
Terence Gaffney, Multiplicities and equisingularity of ICIS germs, Invent. Math. 123 (1996), no. 2, 209–220. MR 1374196, DOI 10.1007/s002220050022
M. Gromov, Convex sets and Kähler manifolds, Advances in differential geometry and topology, World Sci. Publ., Teaneck, NJ, 1990, pp. 1–38. MR 1095529
Joe Harris, Algebraic geometry, Graduate Texts in Mathematics, vol. 133, Springer-Verlag, New York, 1995. A first course; Corrected reprint of the 1992 original. MR 1416564
Robin Hartshorne, Varieties of small codimension in projective space, Bull. Amer. Math. Soc. 80 (1974), 1017–1032. MR 384816, DOI 10.1090/S0002-9904-1974-13612-8
A. P. Heron, Matroid polynomials, Combinatorics (Proc. Conf. Combinatorial Math., Math. Inst., Oxford, 1972) Inst. Math. Appl., Southend-on-Sea, 1972, pp. 164–202. MR 0340058
Craig Huneke and Irena Swanson, Integral closure of ideals, rings, and modules, London Mathematical Society Lecture Note Series, vol. 336, Cambridge University Press, Cambridge, 2006. MR 2266432
Jean-Pierre Jouanolou, Théorèmes de Bertini et applications, Progress in Mathematics, vol. 42, Birkhäuser Boston, Inc., Boston, MA, 1983 (French). MR 725671
K. Kaveh and A. G. Khovanskii, Newton-Okounkov bodies, semigroups of integral points, graded algebras and intersection theory, Preprint: arXiv:0904.3350v2.
Yu. D. Burago and V. A. Zalgaller, Geometric inequalities, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 285, Springer-Verlag, Berlin, 1988. Translated from the Russian by A. B. Sosinskiĭ; Springer Series in Soviet Mathematics. MR 936419, DOI 10.1007/978-3-662-07441-1
A. G. Kouchnirenko, Polyèdres de Newton et nombres de Milnor, Invent. Math. 32 (1976), no. 1, 1–31 (French). MR 419433, DOI 10.1007/BF01389769
Joseph P. S. Kung, The geometric approach to matroid theory, Gian-Carlo Rota on combinatorics, Contemp. Mathematicians, Birkhäuser Boston, Boston, MA, 1995, pp. 604–622. MR 1392975
Robert Lazarsfeld, Positivity in algebraic geometry. I, Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics [Results in Mathematics and Related Areas. 3rd Series. A Series of Modern Surveys in Mathematics], vol. 48, Springer-Verlag, Berlin, 2004. Classical setting: line bundles and linear series. MR 2095471, DOI 10.1007/978-3-642-18808-4
Robert Lazarsfeld and Mircea Mustaţă, Convex bodies associated to linear series, Ann. Sci. Éc. Norm. Supér. (4) 42 (2009), no. 5, 783–835 (English, with English and French summaries). MR 2571958, DOI 10.24033/asens.2109
R. D. MacPherson, Chern classes for singular algebraic varieties, Ann. of Math. (2) 100 (1974), 423–432. MR 361141, DOI 10.2307/1971080
David Marker, Model theory, Graduate Texts in Mathematics, vol. 217, Springer-Verlag, New York, 2002. An introduction. MR 1924282
D. G. Northcott and D. Rees, Reductions of ideals in local rings, Proc. Cambridge Philos. Soc. 50 (1954), 145–158. MR 59889, DOI 10.1017/s0305004100029194
Andrei Okounkov, Brunn-Minkowski inequality for multiplicities, Invent. Math. 125 (1996), no. 3, 405–411. MR 1400312, DOI 10.1007/s002220050081
James Oxley, Matroid theory, 2nd ed., Oxford Graduate Texts in Mathematics, vol. 21, Oxford University Press, Oxford, 2011. MR 2849819, DOI 10.1093/acprof:oso/9780198566946.001.0001
Peter Orlik and Louis Solomon, Combinatorics and topology of complements of hyperplanes, Invent. Math. 56 (1980), no. 2, 167–189. MR 558866, DOI 10.1007/BF01392549
Peter Orlik and Hiroaki Terao, Arrangements of hyperplanes, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 300, Springer-Verlag, Berlin, 1992. MR 1217488, DOI 10.1007/978-3-662-02772-1
Richard Randell, Morse theory, Milnor fibers and minimality of hyperplane arrangements, Proc. Amer. Math. Soc. 130 (2002), no. 9, 2737–2743. MR 1900880, DOI 10.1090/S0002-9939-02-06412-2
Ronald C. Read, An introduction to chromatic polynomials, J. Combinatorial Theory 4 (1968), 52–71. MR 224505
D. Rees and R. Y. Sharp, On a theorem of B. Teissier on multiplicities of ideals in local rings, J. London Math. Soc. (2) 18 (1978), no. 3, 449–463. MR 518229, DOI 10.1112/jlms/s2-18.3.449
Gian-Carlo Rota, Combinatorial theory, old and new, Actes du Congrès International des Mathématiciens (Nice, 1970) Gauthier-Villars, Paris, 1971, pp. 229–233. MR 0505646
Pierre Samuel, La notion de multiplicité en algèbre et en géométrie algébrique, J. Math. Pures Appl. (9) 30 (1951), 159–205 (French). MR 48103
Rolf Schneider, Convex bodies: the Brunn-Minkowski theory, Encyclopedia of Mathematics and its Applications, vol. 44, Cambridge University Press, Cambridge, 1993. MR 1216521, DOI 10.1017/CBO9780511526282
Igor R. Shafarevich, Basic algebraic geometry. 1, 2nd ed., Springer-Verlag, Berlin, 1994. Varieties in projective space; Translated from the 1988 Russian edition and with notes by Miles Reid. MR 1328833
G. C. Shephard, Inequalities between mixed volumes of convex sets, Mathematika 7 (1960), 125–138. MR 146736, DOI 10.1112/S0025579300001674
Richard P. Stanley, Log-concave and unimodal sequences in algebra, combinatorics, and geometry, Graph theory and its applications: East and West (Jinan, 1986) Ann. New York Acad. Sci., vol. 576, New York Acad. Sci., New York, 1989, pp. 500–535. MR 1110850, DOI 10.1111/j.1749-6632.1989.tb16434.x
Richard P. Stanley, Foundations I and the development of algebraic combinatorics, Gian-Carlo Rota on combinatorics, Contemp. Mathematicians, Birkhäuser Boston, Boston, MA, 1995, pp. 105–107. MR 1392967
Richard P. Stanley, Positivity problems and conjectures in algebraic combinatorics, Mathematics: frontiers and perspectives, Amer. Math. Soc., Providence, RI, 2000, pp. 295–319. MR 1754784
Richard P. Stanley, An introduction to hyperplane arrangements, Geometric combinatorics, IAS/Park City Math. Ser., vol. 13, Amer. Math. Soc., Providence, RI, 2007, pp. 389–496. MR 2383131, DOI 10.1090/pcms/013/08
Bernard Teissier, Cycles évanescents, sections planes et conditions de Whitney, Singularités à Cargèse (Rencontre Singularités Géom. Anal., Inst. Études Sci., Cargèse, 1972) Astérisque, Nos. 7 et 8, Soc. Math. France, Paris, 1973, pp. 285–362 (French). MR 0374482
David Eisenbud and Harold I. Levine, An algebraic formula for the degree of a $C^{\infty }$ map germ, Ann. of Math. (2) 106 (1977), no. 1, 19–44. MR 467800, DOI 10.2307/1971156
Bernard Teissier, Du théorème de l’index de Hodge aux inégalités isopérimétriques, C. R. Acad. Sci. Paris Sér. A-B 288 (1979), no. 4, A287–A289 (French, with English summary). MR 524795
Bernard Teissier, Variétés polaires. II. Multiplicités polaires, sections planes, et conditions de Whitney, Algebraic geometry (La Rábida, 1981) Lecture Notes in Math., vol. 961, Springer, Berlin, 1982, pp. 314–491 (French). MR 708342, DOI 10.1007/BFb0071291
Ngô Viêt Trung, Positivity of mixed multiplicities, Math. Ann. 319 (2001), no. 1, 33–63. MR 1812818, DOI 10.1007/PL00004429
Ngo Viet Trung and Jugal Verma, Mixed multiplicities of ideals versus mixed volumes of polytopes, Trans. Amer. Math. Soc. 359 (2007), no. 10, 4711–4727. MR 2320648, DOI 10.1090/S0002-9947-07-04054-8
D. J. A. Welsh, Matroid theory, L. M. S. Monographs, No. 8, Academic Press [Harcourt Brace Jovanovich, Publishers], London-New York, 1976. MR 0427112