On Stanley's chromatic symmetric function and clawfree graphs (Q1301848): Difference between revisions

A proper coloring of a simple graph \(G\) (without loops and multiple edges) with vertex set \(V=\{v_1,\ldots,v_d\}\) is a function \(\kappa: V\to {\mathbb{N}}^+\) such that \(\kappa(u)\not=\kappa(v)\) if \(u\) and \(v\) are vertices of an edge of \(G\). Stanley associated to \(G\) the symmetric function \(X_G=X_G(x_1,x_2,\ldots)=\sum x_{\kappa(v_1)}\ldots x_{\kappa(v_d)}\), where the sum ranges over all proper colorings \(\kappa\) of \(G\). He also conjectured that if \(G\) is a claw-free graph (i.e. does not contain \(K_{1,3}\) as an induced subgraph) then the function \(X_G\) is Schur positive, i.e. is a nonnegative linear combination of Schur functions. A statement which is equivalent to the Stanley conjecture is that every minor of the Toeplitz matrix \(A=[e_{j-i}^G]_{i,j\geq 0}\) is a polynomial with nonnegative coefficients, where \(e_n^G=e_n^G(v_1,\ldots,v_d)= \sum_S(\prod_{v\in S}v)\), \(S\) runs over all \(n\)-element stable subsets of \(V\), and ``stable'' means that no two vertices are joined by an edge. One of the main results of the paper under review is a combinatorial proof that the \(2\times 2\) minors of the matrix \(A\) have nonnegative coefficients. This provides supportive evidences for the Stanley conjecture, generalizes a result of Krattenthaler and gives a new proof of a result of Hamidoune that the stable set polynomial \(\sum_{n\geq 0}e_n^G(1,1,\ldots,1)t^n\) related with a claw-free graph is log-concave. Finally, the author characterizes the claw-free graphs in terms of cardinalities of stable sets.