Expansions of chromatic polynomials and log-concavity

Brenti, Francesco

doi:10.1090/S0002-9947-1992-1069745-7

Expansions of chromatic polynomials and log-concavity
HTML articles powered by AMS MathViewer

by Francesco Brenti PDF

Trans. Amer. Math. Soc. 332 (1992), 729-756 Request permission

Abstract:

In this paper we present several results and open problems about logconcavity properties of sequences associated with graph colorings. Five polynomials intimately related to the chromatic polynomial of a graph are introduced and their zeros, combinatorial and log-concavity properties are studied. Four of these polynomials have never been considered before in the literature and some yield new expansions for the chromatic polynomial.

References

Ruth A. Bari, Regular major maps of at most $19$ regions and their $Q$-chromials, J. Combinatorial Theory Ser. B 12 (1972), 132–142. MR 294171, DOI 10.1016/0095-8956(72)90017-2
Emile Bertin and Radu Theodorescu, On the unimodality of discrete probability measures, Math. Z. 201 (1989), no. 1, 131–137. MR 990194, DOI 10.1007/BF01162000
Norman Biggs, Algebraic graph theory, Cambridge Tracts in Mathematics, No. 67, Cambridge University Press, London, 1974. MR 0347649
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. MR 1502436, DOI 10.2307/1967597

On the polynomial expressions for the number of ways of coloring a map

3

G. D. Birkhoff and D. C. Lewis, Chromatic polynomials, Trans. Amer. Math. Soc. 60 (1946), 355–451. MR 18401, DOI 10.1090/S0002-9947-1946-0018401-4
J. A. Bondy and U. S. R. Murty, Graph theory with applications, American Elsevier Publishing Co., Inc., New York, 1976. MR 0411988
Francesco Brenti, Unimodal, log-concave and Pólya frequency sequences in combinatorics, Mem. Amer. Math. Soc. 81 (1989), no. 413, viii+106. MR 963833, DOI 10.1090/memo/0413
Francesco Brenti, Unimodal, log-concave and Pólya frequency sequences in combinatorics, Mem. Amer. Math. Soc. 81 (1989), no. 413, viii+106. MR 963833, DOI 10.1090/memo/0413
Francesco Brenti, Unimodal polynomials arising from symmetric functions, Proc. Amer. Math. Soc. 108 (1990), no. 4, 1133–1141. MR 993741, DOI 10.1090/S0002-9939-1990-0993741-2
Francesco Brenti, Log-concavity and combinatorial properties of Fibonacci lattices, European J. Combin. 12 (1991), no. 6, 459–476. MR 1136388, DOI 10.1016/S0195-6698(13)80097-2

Unimodality, permutation enumeration, and symmetric functions

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. MR 911049, DOI 10.1090/S0002-9939-1987-0911049-8
Louis Comtet, Advanced combinatorics, Revised and enlarged edition, D. Reidel Publishing Co., Dordrecht, 1974. The art of finite and infinite expansions. MR 0460128
Medha Dhurandhar, Characterization of quadratic and cubic $\sigma$-polynomials, J. Combin. Theory Ser. B 37 (1984), no. 3, 210–220. MR 769363, DOI 10.1016/0095-8956(84)90053-4
G. A. Dirac, On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg 25 (1961), 71–76. MR 130190, DOI 10.1007/BF02992776
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. MR 0360288
Roberto W. Frucht and Reinaldo E. Giudici, Some chromatically unique graphs with seven points, Ars Combin. 16 (1983), no. A, 161–172. MR 737088
Fănică Gavril, The intersection graphs of subtrees in trees are exactly the chordal graphs, J. Combinatorial Theory Ser. B 16 (1974), 47–56. MR 332541, DOI 10.1016/0095-8956(74)90094-x
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. MR 816964
P. C. Gilmore and A. J. Hoffman, A characterization of comparability graphs and of interval graphs, Canadian J. Math. 16 (1964), 539–548. MR 175811, DOI 10.4153/CJM-1964-055-5
Reinaldo E. Giudici and Ramon M. Vinke, A table of chromatic polynomials, J. Combin. Inform. System Sci. 5 (1980), no. 4, 323–350. MR 609820
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. MR 429578, DOI 10.1090/S0002-9939-1975-0429578-4
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. MR 0541009, DOI 10.1016/0095-8956(78)90033-3
Frank Harary, Graph theory, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London 1969. MR 0256911

Inequalities

André Joyal, Une théorie combinatoire des séries formelles, Adv. in Math. 42 (1981), no. 1, 1–82 (French, with English summary). MR 633783, DOI 10.1016/0001-8708(81)90052-9
Samuel Karlin, Total positivity. Vol. I, Stanford University Press, Stanford, Calif., 1968. MR 0230102
Robert R. Korfhage, $\sigma$-polynomials and graph coloring, J. Combinatorial Theory Ser. B 24 (1978), no. 2, 137–153. MR 491301, DOI 10.1016/0095-8956(78)90015-1
Robert R. Korfhage, A note on quadratic $\sigma$-polynomials, Discrete Math. 69 (1988), no. 2, 195–196. MR 937783, DOI 10.1016/0012-365X(88)90018-0
Albert Nijenhuis, On permanents and the zeros of rook polynomials, J. Combinatorial Theory Ser. A 21 (1976), no. 2, 240–244. MR 416936, DOI 10.1016/0097-3165(76)90068-6
Kathleen M. O’Hara, Unimodality of Gaussian coefficients: a constructive proof, J. Combin. Theory Ser. A 53 (1990), no. 1, 29–52. MR 1031611, DOI 10.1016/0097-3165(90)90018-R

Problems and theorems in analysis

Robert A. Proctor, Representations of ${\mathfrak {s}}{\mathfrak {l}}(2,\,\textbf {C})$ on posets and the Sperner property, SIAM J. Algebraic Discrete Methods 3 (1982), no. 2, 275–280. MR 655567, DOI 10.1137/0603026
Robert A. Proctor, Solution of two difficult combinatorial problems with linear algebra, Amer. Math. Monthly 89 (1982), no. 10, 721–734. MR 683197, DOI 10.2307/2975833
Ronald C. Read, An introduction to chromatic polynomials, J. Combinatorial Theory 4 (1968), 52–71. MR 224505
Ronald C. Read, A large family of chromatic polynomials, Proceedings of the Third Caribbean Conference on Combinatorics and Computing (Bridgetown, 1981) University of the West Indies, Cave Hill Campus, Barbados, 1981, pp. 23–41. MR 657188

Some applications of computers in graph theory

Donald J. Rose, Triangulated graphs and the elimination process, J. Math. Anal. Appl. 32 (1970), 597–609. MR 270957, DOI 10.1016/0022-247X(70)90282-9
Bruce E. Sagan, Inductive and injective proofs of log concavity results, Discrete Math. 68 (1988), no. 2-3, 281–292. MR 926131, DOI 10.1016/0012-365X(88)90120-3

Log-concave sequences of symmetric functions and analogs of the Jacobi-Trudi determinant

Richard P. Stanley, Ordered structures and partitions, Memoirs of the American Mathematical Society, No. 119, American Mathematical Society, Providence, R.I., 1972. MR 0332509
R. P. Stanley, Supersolvable lattices, Algebra Universalis 2 (1972), 197–217. MR 309815, DOI 10.1007/BF02945028
Richard P. Stanley, Acyclic orientations of graphs, Discrete Math. 5 (1973), 171–178. MR 317988, DOI 10.1016/0012-365X(73)90108-8
Richard P. Stanley, Balanced Cohen-Macaulay complexes, Trans. Amer. Math. Soc. 249 (1979), no. 1, 139–157. MR 526314, DOI 10.1090/S0002-9947-1979-0526314-6
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. MR 588199
Richard P. Stanley, Unimodality and Lie superalgebras, Stud. Appl. Math. 72 (1985), no. 3, 263–281. MR 790132, DOI 10.1002/sapm1985723263

Enumerative combinatorics

Generalized

vectors, intersection cohomology of toric varieties, and related results

11

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
Dennis Stanton and Dennis White, Constructive combinatorics, Undergraduate Texts in Mathematics, Springer-Verlag, New York, 1986. MR 843332, DOI 10.1007/978-1-4612-4968-9
W. T. Tutte, The golden ratio in the theory of chromatic polynomials, Ann. New York Acad. Sci. 175 (1970), 391–402. MR 265218
W. T. Tutte, Chromials, Hypergraph Seminar (Proc. First Working Sem., Ohio State Univ., Columbus, Ohio, 1972; dedicated to Arnold Ross), Lecture Notes in Math., Vol. 411, Springer, Berlin, 1974, pp. 243–266. MR 0369134

Enumerative combinatorics of partially ordered sets, and total positivity of Hadamard products

David G. Wagner, The partition polynomial of a finite set system, J. Combin. Theory Ser. A 56 (1991), no. 1, 138–159. MR 1082848, DOI 10.1016/0097-3165(91)90027-E
David G. Wagner, Total positivity of Hadamard products, J. Math. Anal. Appl. 163 (1992), no. 2, 459–483. MR 1145841, DOI 10.1016/0022-247X(92)90261-B
D. J. A. Welsh, Matroid theory, L. M. S. Monographs, No. 8, Academic Press [Harcourt Brace Jovanovich, Publishers], London-New York, 1976. MR 0427112
Dennis E. White, Monotonicity and unimodality of the pattern inventory, Adv. in Math. 38 (1980), no. 1, 101–108. MR 594996, DOI 10.1016/0001-8708(80)90059-6
Hassler Whitney, The coloring of graphs, Ann. of Math. (2) 33 (1932), no. 4, 688–718. MR 1503085, DOI 10.2307/1968214
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. MR 0463010
Shao Ji Xu, On $\sigma$-polynomials, Discrete Math. 69 (1988), no. 2, 189–194. MR 937782, DOI 10.1016/0012-365X(88)90017-9
Doron Zeilberger, Kathy O’Hara’s constructive proof of the unimodality of the Gaussian polynomials, Amer. Math. Monthly 96 (1989), no. 7, 590–602. MR 1008789, DOI 10.2307/2325177