A321979 Number of e-positive simple labeled graphs on n vertices.

1, 1, 2, 8, 60, 899

Offset: 0

Author

Gus Wiseman, Nov 23 2018

Keywords

• nonn
• more

Comments

A stable partition of a graph is a set partition of the vertices where no edge has both ends in the same block. The chromatic symmetric function is given by X_G = Sum_p m(t(p)) where the sum is over all stable partitions of G, t(p) is the integer partition whose parts are the block-sizes of p, and m is augmented monomial symmetric functions (see A321895). A graph is e-positive if, in the expansion of its chromatic symmetric function in terms of elementary symmetric functions, all coefficients are nonnegative.

Examples

			The 4 non-e-positive simple labeled graphs on 4 vertices are:
  {{1,2},{1,3},{1,4}}
  {{1,2},{2,3},{2,4}}
  {{1,3},{2,3},{3,4}}
  {{1,4},{2,4},{3,4}}
		

Links

• Richard P. Stanley, A symmetric function generalization of the chromatic polynomial of a graph, Advances in Math. 111 (1995), 166-194.
• Richard P. Stanley, Graph colorings and related symmetric functions: ideas and applications, Discrete Mathematics 193 (1998), 267-286.
• Richard P. Stanley and John R. Stembridge, On immanants of Jacobi-Trudi matrices and permutations with restricted position, Journal of Combinatorial Theory Series A 62-2 (1993), 261-279.
• Gus Wiseman, Enumeration of paths and cycles and e-coefficients of incomparability graphs, arXiv:0709.0430 [math.CO], 2007.
• Gus Wiseman, The a(4) = 60 e-positive simple labeled graphs.

Crossrefs

Cf. A000569, A006125, A229048, A240936, A277203, A321895, A321911, A321918, A321914, A321931, A321980, A321981, A321982.