Acyclic orientation polynomials and the sink theorem for chromatic symmetric functions. (English) Zbl 1447.05210
Summary: We define the acyclic orientation polynomial of a graph to be the generating function for the sinks of its acyclic orientations. R. P. Stanley [Discrete Math. 306, No. 10–11, 905–909 (2006; Zbl 1094.05031)] proved that the number of acyclic orientations is equal to the chromatic polynomial evaluated at \(-1\) up to sign. Motivated by this result, we develop “acyclic orientation” analogues for theorems concerning the chromatic polynomial by G. D. Birkhoff [Ann. Math. (2) 14, 42–46 (1912; JFM 43.0574.02)], H. Whitney [Bull. Am. Math. Soc. 38, 572–579 (1932; Zbl 0005.14602)], and C. Greene and T. Zaslavsky [Trans. Am. Math. Soc. 280, 97–126 (1983; Zbl 0539.05024)]. As the main application, we provide a new proof for Stanley’s sink theorem for chromatic symmetric functions \(X_G\), which gives a relation between the number of acyclic orientations with a fixed number of sinks and the coefficients in the expansion of \(X_G\) with respect to elementary symmetric functions.
Keywords:
acyclic orientations; generating function for sinks; deletion-contraction recursion; sink theorem; chromatic symmetric functionsReferences:
| [1] | O. Bernardi and P. Nadeau. “Combinatorial reciprocity for the chromatic polynomial and the chromatic symmetric function”.Discrete Math.343.10 (2020).Link. · Zbl 1445.05052 |
| [2] | G. Birkhoff. “A determinant formula for the number of ways of coloring a map”.Ann. of Math.14.1/4 (1912), pp. 42-46. · JFM 43.0574.02 |
| [3] | D. Eisenstat and G. Gordon. “Non-isomorphic caterpillars with identical subtree data”. Discrete math.306.8-9 (2006), pp. 827-830.Link. · Zbl 1091.05020 |
| [4] | D. Gebhard and B. Sagan. “Sinks in acyclic orientations of graphs”.J. Combin. Theory Ser. B 80.1 (2000), pp. 130-146.Link. · Zbl 1023.05069 |
| [5] | D. Gebhard and B. Sagan. “A chromatic symmetric function in noncommuting variables”. J. Algebraic Combin.13.3 (2001), pp. 227-255.Link. · Zbl 0979.05105 |
| [6] | C. Greene and T. Zaslavsky. “On the interpretation of Whitney numbers through arrangements of hyperplanes, zonotopes, non-Radon partitions, and orientations of graphs”.Trans. Amer. Math. Soc.280.1 (1983), pp. 97-126.Link. · Zbl 0539.05024 |
| [7] | B. Lass. “Orientations acycliques et le polynôme chromatique”.European J. Combin.22.8 (2001), pp. 1101-1123.Link. · Zbl 0990.05063 |
| [8] | J. Martin, M. Morin, and J. Wagner. “On distinguishing trees by their chromatic symmetric functions”.J. Combin. Theory Ser. A115.2 (2008), pp. 237-253.Link. · Zbl 1133.05020 |
| [9] | R. Stanley. “Acyclic orientations of graphs”.Discrete Math.5.2 (1973), pp. 171-178.Link. · Zbl 0258.05113 |
| [10] | R. Stanley. “A symmetric function generalization of the chromatic polynomial of a graph”. Adv. Math.111.1 (1995), pp. 166-194.Link. · Zbl 0831.05027 |
| [11] | R. Stanley.Enumerative Combinatorics, Vol. 2. Cambridge Stud. Adv. Math, 1999.Link. · Zbl 0928.05001 |
| [12] | R. Stanley. “A Chromatic Symmetric Function Conjecture”.Talk slide in Special Session on My Favorite Graph Theory Conjectures, AMS Winter Meeting(2012).Link. |
| [13] | H. |
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.
