Thesis (633 Kb)  Free access
Highlights
More informations
Title 
Positivity for Stanley's chromatic functions 

Author  
Director  
Defense  Thèse de doctorat : Univ. Genève, 2016  Sc. 4969  2016/08/23  
Abstract  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 Schurcoefficients 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 Lindströ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.  
Identifiers  URN: urn:nbn:ch:unige876003  
Full text  
Structures  
Citation (ISO format)  PAUNOV, Alexander. Positivity for Stanley's chromatic functions. Université de Genève. Thèse, 2016. https://archiveouverte.unige.ch/unige:87600 