Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: A quasisymmetric function generalization of the chromatic symmetric function. | A quasisymmetric function generalization of the chromatic symmetric function Brandon Humpert University of Kansas Lawrence KS bhumpert@ Submitted May 5 2010 Accepted Feb 3 2011 Published Feb 14 2011 Mathematics Subject Classification 05C31 Abstract The chromatic symmetric function Xg of a graph G was introduced by Stanley. In this paper we introduce a quasisymmetric generalization xG called the k-chromatic quasisymmetric function of G and show that it is positive in the fundamental basis for the quasisymmetric functions. Following the specialization of Xg to Xg A the chromatic polynomial we also define a generalization xG A and show that evaluations of this polynomial for negative values generalize a theorem of Stanley relating acyclic orientations to the chromatic polynomial. 1 Introduction The symbol P will denote the positive integers. Let G V E be a finite simple graph with vertices V n 1 2 . n . A proper coloring of G is a function K V P such that K i K j whenever ij G E. Stanley 5 introduced the chromatic symmetric function Xg Xg Xi X2 . 52 Xk i XK n proper colorings K in commuting indeterminates x1 x2 . This invariant is a symmetric function because permuting the colors does not change whether or not a given coloring is proper. Moreover XG generalizes the classical chromatic polynomial XG A which can be obtained from XG by setting k of the indeterminates to 1 and the others to 0 . This paper is about a quasisymmetric function generalization of XG which arose in the following context. Recall that the Hasse diagram of a poset P is the acyclic directed graph with an edge x y for each covering relation x y of P. It is natural to ask which undirected graphs G are Hasse graphs . admit orientations that are Hasse diagrams of posets. O. Pretzel 3 gave the following answer to this question. Call a THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P31 1 directed graph k-balanced Pretzel used the term k-good if for every cycle C of the underlying undirected
