Positivity for Stanley's chromatic functions

Diplôme Thèse Positivity for Stanley's chromatic functions eng 2016-08-23 author Paunov Alexander 757532 director Szenes Andras 664272 10.13097/archive-ouverte/unige:87600 urn:nbn:ch:unige-876003 Sc. 4969 This dissertation is dedicated to the study of positivity phenomena for the coefficients of the chromatic symmetric function of a graph. This function was introduced by Stanley in 1995 as a generalization of the chromatic polynomial of a graph. Stanley considered the expansion of the chromatic symmetric function in terms of various bases of symmetric functions, and conjectured the positivity of its coefficients in the basis of the elementary symmetric functions in the case of the incomparability graphs of (3 + 1)-free posets. The conjecture has not yet been proven, but has been checked for small graphs, and proven for certain families of graphs. The strongest general result in this direction was obtained by Gasharov. He proved a weaker statement, Schur positivity of the incomparability graphs of (3 + 1)-free posets. The strongest result on the positivity of the coefficients in the basis of the elementary symmetric functions was obtained by Stanley, who proved the positivity of certain sums of these coefficients by linking them to acyclic orientations of the incomparability graph. In this thesis we give a new proof of Gasharov's theorem, which presents a combinatorial interpretation of the Schur-coefficients in terms of planar networks. Compared to Gasharov's proof, it gives a clearer visual illustration of the cancellation procedures and is quite similar in spirit to the proof of monomial positivity of Schur functions via the Lindström–Gessel–Viennot Lemma. This construction led us to reconsider another idea of Stanley: instead of working with the chromatic symmetric function of a graph directly, we analyze certain analogs of the symmetric functions attached to graphs. We introduce a new combinatorial object: the correct sequences of unit interval orders, and using these, in certain cases, we succeed to construct combinatorial models of the coefficients appearing in Stanley's conjecture. Our main result is the proof of positivity of the coefficients c_{n−k,1^k} , c_{n−2,2}, c_{n−3,2,1} and c_{2^k,1^{n−2k}} of the expansion of the chromatic symmetric function in terms of the basis of the elementary symmetric polynomials for the case of (3 + 1)-free posets. Dewey 510 25 Section de mathématiques 11 false a0ce380f-1413-44b1-8582-2d8801aa91ac Thesis Public Thesis_Paunov.pdf 648388 application/pdf openAccess Faculté des sciences / Section de mathématiques

Title	Published in	Access level	OA Policy	Year	Views	Downloads

Positivity for Stanley's chromatic functions				2016	1,237	303

Archive ouverte UNIGE

Paunov, Alexander