×

Expansions of chromatic polynomials and log-concavity. (English) Zbl 0757.05052

In 1989, R. Stanley gave a survey of results about log-concave and unimodal sequences in algebra, combinatorics, and geometry. In the present paper the author presents several results and open problems about log-concavity properties of sequences associated with graph-colourings. He introduces five polynomials intimately related to the chromatic polynomial of a graph, and studies their zeros and log-concavity properties. Four of these are considered here for the first time, and give new expansions for the chromatic polynomial.

MSC:

05C15 Coloring of graphs and hypergraphs
05A20 Combinatorial inequalities
05A19 Combinatorial identities, bijective combinatorics
05A15 Exact enumeration problems, generating functions
26C10 Real polynomials: location of zeros
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ruth A. Bari, Regular major maps of at most 19 regions and their \?-chromials, J. Combinatorial Theory Ser. B 12 (1972), 132 – 142. · Zbl 0211.56603
[2] Emile Bertin and Radu Theodorescu, On the unimodality of discrete probability measures, Math. Z. 201 (1989), no. 1, 131 – 137. · Zbl 0648.60013 · doi:10.1007/BF01162000
[3] Norman Biggs, Algebraic graph theory, Cambridge University Press, London, 1974. Cambridge Tracts in Mathematics, No. 67. · Zbl 0284.05101
[4] George D. Birkhoff, A determinant formula for the number of ways of coloring a map, Ann. of Math. (2) 14 (1912/13), no. 1-4, 42 – 46. · JFM 43.0574.02 · doi:10.2307/1967597
[5] -, On the polynomial expressions for the number of ways of coloring a map, Ann. Scuola Norm. Sup. (Pisa) (2) 3 (1934), 85-104. · Zbl 0008.22601
[6] G. D. Birkhoff and D. C. Lewis, Chromatic polynomials, Trans. Amer. Math. Soc. 60 (1946), 355 – 451. · Zbl 0060.41601
[7] J. A. Bondy and U. S. R. Murty, Graph theory with applications, American Elsevier Publishing Co., Inc., New York, 1976. · Zbl 1226.05083
[8] Francesco Brenti, Unimodal, log-concave and Pólya frequency sequences in combinatorics, Mem. Amer. Math. Soc. 81 (1989), no. 413, viii+106. · Zbl 0697.05011 · doi:10.1090/memo/0413
[9] Francesco Brenti, Unimodal, log-concave and Pólya frequency sequences in combinatorics, Mem. Amer. Math. Soc. 81 (1989), no. 413, viii+106. · Zbl 0697.05011 · doi:10.1090/memo/0413
[10] Francesco Brenti, Unimodal polynomials arising from symmetric functions, Proc. Amer. Math. Soc. 108 (1990), no. 4, 1133 – 1141. · Zbl 0701.05003
[11] Francesco Brenti, Log-concavity and combinatorial properties of Fibonacci lattices, European J. Combin. 12 (1991), no. 6, 459 – 476. · Zbl 0745.06002 · doi:10.1016/S0195-6698(13)80097-2
[12] -, Unimodality, permutation enumeration, and symmetric functions, Pacific J. Math. (to appear). · Zbl 0805.05089
[13] Lynne M. Butler, A unimodality result in the enumeration of subgroups of a finite abelian group, Proc. Amer. Math. Soc. 101 (1987), no. 4, 771 – 775. · Zbl 0647.20053
[14] Louis Comtet, Advanced combinatorics, Revised and enlarged edition, D. Reidel Publishing Co., Dordrecht, 1974. The art of finite and infinite expansions. · Zbl 0283.05001
[15] Medha Dhurandhar, Characterization of quadratic and cubic \?-polynomials, J. Combin. Theory Ser. B 37 (1984), no. 3, 210 – 220. · Zbl 0554.05030 · doi:10.1016/0095-8956(84)90053-4
[16] G. A. Dirac, On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg 25 (1961), 71 – 76. · Zbl 0098.14703 · doi:10.1007/BF02992776
[17] D. Foata and M. P. Schützenberger, On the rook polynomials of Ferrers relations, Combinatorial theory and its applications, II (Proc. Colloq., Balatonfüred, 1969) North-Holland, Amsterdam, 1970, pp. 413 – 436. · Zbl 0217.01802
[18] Roberto W. Frucht and Reinaldo E. Giudici, Some chromatically unique graphs with seven points, Ars Combin. 16 (1983), no. A, 161 – 172. · Zbl 0536.05026
[19] Fănică Gavril, The intersection graphs of subtrees in trees are exactly the chordal graphs, J. Combinatorial Theory Ser. B 16 (1974), 47 – 56. · Zbl 0266.05101
[20] Dieter Gernert, A survey of partial proofs for Read’s conjecture and some recent results, IX symposium on operations research. Part I. Sections 1 – 4 (Osnabrück, 1984) Methods Oper. Res., vol. 49, Athenäum/Hain/Hanstein, Königstein, 1985, pp. 233 – 238. · Zbl 0582.05027
[21] P. C. Gilmore and A. J. Hoffman, A characterization of comparability graphs and of interval graphs, Canad. J. Math. 16 (1964), 539 – 548. · Zbl 0121.26003 · doi:10.4153/CJM-1964-055-5
[22] Reinaldo E. Giudici and Ramon M. Vinke, A table of chromatic polynomials, J. Combin. Inform. System Sci. 5 (1980), no. 4, 323 – 350. · Zbl 0454.05026
[23] Jay R. Goldman, J. T. Joichi, and Dennis E. White, Rook theory. I. Rook equivalence of Ferrers boards, Proc. Amer. Math. Soc. 52 (1975), 485 – 492. · Zbl 0312.05002
[24] Jay R. Goldman, J. T. Joichi, and Dennis E. White, Rook theory. III. Rook polynomials and the chromatic structure of graphs, J. Combin. Theory Ser. B 25 (1978), no. 2, 135 – 142. , https://doi.org/10.1016/0095-8956(78)90033-3 Jay R. Goldman, J. T. Joichi, and Dennis E. White, Rook theory. IV. Orthogonal sequences of Rook polynomials, Studies in Appl. Math. 56 (1976/77), no. 3, 267 – 272. · Zbl 0336.05005
[25] Frank Harary, Graph theory, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London, 1969. · Zbl 0182.57702
[26] G. H. Hardy, J. E. Littlewood, and G. Pólya, Inequalities, 2nd ed., Cambridge Univ. Press, Cambridge, 1952. · Zbl 0047.05302
[27] André Joyal, Une théorie combinatoire des séries formelles, Adv. in Math. 42 (1981), no. 1, 1 – 82 (French, with English summary). · Zbl 0491.05007 · doi:10.1016/0001-8708(81)90052-9
[28] Samuel Karlin, Total positivity. Vol. I, Stanford University Press, Stanford, Calif, 1968.
[29] Robert R. Korfhage, \?-polynomials and graph coloring, J. Combinatorial Theory Ser. B 24 (1978), no. 2, 137 – 153. · Zbl 0845.05043
[30] Robert R. Korfhage, A note on quadratic \?-polynomials, Discrete Math. 69 (1988), no. 2, 195 – 196. · Zbl 0658.05026 · doi:10.1016/0012-365X(88)90018-0
[31] Albert Nijenhuis, On permanents and the zeros of rook polynomials, J. Combinatorial Theory Ser. A 21 (1976), no. 2, 240 – 244. · Zbl 0342.05005
[32] Kathleen M. O’Hara, Unimodality of Gaussian coefficients: a constructive proof, J. Combin. Theory Ser. A 53 (1990), no. 1, 29 – 52. · Zbl 0697.05002 · doi:10.1016/0097-3165(90)90018-R
[33] G. Pólya and G. Szegö, Problems and theorems in analysis, Vols. I and II, Springer-Verlag, Berlin and Heidelberg, 1976. · Zbl 0338.00001
[34] Robert A. Proctor, Representations of \?\?(2,\?) on posets and the Sperner property, SIAM J. Algebraic Discrete Methods 3 (1982), no. 2, 275 – 280. · Zbl 0496.06004 · doi:10.1137/0603026
[35] Robert A. Proctor, Solution of two difficult combinatorial problems with linear algebra, Amer. Math. Monthly 89 (1982), no. 10, 721 – 734. · Zbl 0509.05007 · doi:10.2307/2975833
[36] Ronald C. Read, An introduction to chromatic polynomials, J. Combinatorial Theory 4 (1968), 52 – 71. · Zbl 0173.26203
[37] Ronald C. Read, A large family of chromatic polynomials, Proceedings of the Third Caribbean Conference on Combinatorics and Computing (Bridgetown, 1981) Univ. West Indies, Cave Hill Campus, Barbados, 1981, pp. 23 – 41. · Zbl 0498.05029
[38] -, Some applications of computers in graph theory, Selected Topics in Graph Theory , Academic Press, London, 1978, pp. 417-444.
[39] Donald J. Rose, Triangulated graphs and the elimination process, J. Math. Anal. Appl. 32 (1970), 597 – 609. · Zbl 0216.02602 · doi:10.1016/0022-247X(70)90282-9
[40] Bruce E. Sagan, Inductive and injective proofs of log concavity results, Discrete Math. 68 (1988), no. 2-3, 281 – 292. · Zbl 0658.05003 · doi:10.1016/0012-365X(88)90120-3
[41] -, Log-concave sequences of symmetric functions and analogs of the Jacobi-Trudi determinant, Preprint. · Zbl 0769.05097
[42] Richard P. Stanley, Ordered structures and partitions, American Mathematical Society, Providence, R.I., 1972. Memoirs of the American Mathematical Society, No. 119. · Zbl 0246.05007
[43] R. P. Stanley, Supersolvable lattices, Algebra Universalis 2 (1972), 197 – 217. · Zbl 0256.06002 · doi:10.1007/BF02945028
[44] Richard P. Stanley, Acyclic orientations of graphs, Discrete Math. 5 (1973), 171 – 178. · Zbl 0258.05113 · doi:10.1016/0012-365X(73)90108-8
[45] Richard P. Stanley, Balanced Cohen-Macaulay complexes, Trans. Amer. Math. Soc. 249 (1979), no. 1, 139 – 157. · Zbl 0411.05012
[46] Richard P. Stanley, Unimodal sequences arising from Lie algebras, Combinatorics, representation theory and statistical methods in groups, Lecture Notes in Pure and Appl. Math., vol. 57, Dekker, New York, 1980, pp. 127 – 136. · Zbl 0451.05004
[47] Richard P. Stanley, Unimodality and Lie superalgebras, Stud. Appl. Math. 72 (1985), no. 3, 263 – 281. · Zbl 0614.17004 · doi:10.1002/sapm1985723263
[48] -, Enumerative combinatorics, Vol. 1, Wadsworth and Brooks/Cole, Monterey, Calif., 1986.
[49] -, Generalized \( h\)-vectors, intersection cohomology of toric varieties, and related results, Adv. Stud. Pure Math. 11 (1987), 187-213.
[50] 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. · Zbl 0792.05008 · doi:10.1111/j.1749-6632.1989.tb16434.x
[51] Dennis Stanton and Dennis White, Constructive combinatorics, Undergraduate Texts in Mathematics, Springer-Verlag, New York, 1986. · Zbl 0595.05002
[52] W. T. Tutte, The golden ratio in the theory of chromatic polynomials, Ann. New York Acad. Sci. 175 (1970), 391 – 402. · Zbl 0227.05102
[53] W. T. Tutte, Chromials, Hypergraph Seminar (Proc. First Working Sem., Ohio State Univ., Columbus, Ohio, 1972; dedicated to Arnold Ross), Springer, Berlin, 1974, pp. 243 – 266. Lecture Notes in Math., Vol. 411. · Zbl 0297.05105
[54] D. Wagner, Enumerative combinatorics of partially ordered sets, and total positivity of Hadamard products, Ph.D. Thesis, Massachusetts Institute of Technology, 1989.
[55] David G. Wagner, The partition polynomial of a finite set system, J. Combin. Theory Ser. A 56 (1991), no. 1, 138 – 159. · Zbl 0753.05083 · doi:10.1016/0097-3165(91)90027-E
[56] David G. Wagner, Total positivity of Hadamard products, J. Math. Anal. Appl. 163 (1992), no. 2, 459 – 483. · Zbl 0783.15010 · doi:10.1016/0022-247X(92)90261-B
[57] D. J. A. Welsh, Matroid theory, Academic Press [Harcourt Brace Jovanovich, Publishers], London-New York, 1976. L. M. S. Monographs, No. 8. · Zbl 0343.05002
[58] Dennis E. White, Monotonicity and unimodality of the pattern inventory, Adv. in Math. 38 (1980), no. 1, 101 – 108. · Zbl 0459.05010 · doi:10.1016/0001-8708(80)90059-6
[59] Hassler Whitney, The coloring of graphs, Ann. of Math. (2) 33 (1932), no. 4, 688 – 718. · Zbl 0005.31301 · doi:10.2307/1968214
[60] D. R. Woodall, Zeros of chromatic polynomials, Combinatorial surveys (Proc. Sixth British Combinatorial Conf., Royal Holloway College, Egham, 1977) Academic Press, London, 1977, pp. 199 – 223. · Zbl 0357.05044
[61] Shao Ji Xu, On \?-polynomials, Discrete Math. 69 (1988), no. 2, 189 – 194. · Zbl 0658.05025 · doi:10.1016/0012-365X(88)90017-9
[62] Doron Zeilberger, Kathy O’Hara’s constructive proof of the unimodality of the Gaussian polynomials, Amer. Math. Monthly 96 (1989), no. 7, 590 – 602. · Zbl 0726.05005 · doi:10.2307/2325177
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.