UNIGE document Doctoral Thesis
previous document  unige:87600  next document
add to browser collection
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 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 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:unige-876003
Full text
Thesis (633 Kb) - public document Free access
Structures
Citation
(ISO format)
PAUNOV, Alexander. Positivity for Stanley's chromatic functions. Université de Genève. Thèse, 2016. https://archive-ouverte.unige.ch/unige:87600

161 hits

69 downloads

Update

Deposited on : 2016-09-21

Export document
Format :
Citation style :