|
%I #26 Nov 23 2018 07:58:35
%S 1,2,4,11,33,146,939,10932
%N Number of distinct chromatic symmetric functions realizable by a graph on n vertices.
%C 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). - _Gus Wiseman_, Nov 21 2018
%H Richard P. Stanley, <a href="http://www-math.mit.edu/~rstan/pubs/pubfiles/100.pdf">A symmetric function generalization of the chromatic polynomial of a graph</a>, Advances in Math. 111 (1995), 166-194.
%H Richard P. Stanley, <a href="http://www-math.mit.edu/~rstan/papers/taor.pdf">Graph colorings and related symmetric functions: ideas and applications</a>, Discrete Mathematics 193 (1998), 267-286.
%e For n = 3, under the p basis, the CSF's are: p_{1, 1, 1}, p_{1, 1, 1} - p_{2, 1}, p_{1, 1, 1} - 2p_{2, 1} + p_{3}, p_{1, 1, 1} - 3p_{2, 1} + 2p_{3}.
%e From _Gus Wiseman_, Nov 21 2018: (Start)
%e The a(4) = 11 chromatic symmetric functions (m is the augmented monomial symmetric function basis):
%e m(1111)
%e m(211) + m(1111)
%e 2m(211) + m(1111)
%e m(22) + 2m(211) + m(1111)
%e 3m(211) + m(1111)
%e m(22) + 3m(211) + m(1111)
%e m(31) + 3m(211) + m(1111)
%e 2m(22) + 4m(211) + m(1111)
%e m(22) + m(31) + 4m(211) + m(1111)
%e 2m(22) + 2m(31) + 5m(211) + m(1111)
%e m(4) + 3m(22) + 4m(31) + 6m(211) + m(1111)
%e (End)
%t spsu[_,{}]:={{}};spsu[foo_,set:{i_,___}]:=Join@@Function[s,Prepend[#,s]&/@spsu[Select[foo,Complement[#,Complement[set,s]]=={}&],Complement[set,s]]]/@Cases[foo,{i,___}];
%t chromSF[g_]:=Sum[m[Sort[Length/@stn,Greater]],{stn,spsu[Select[Subsets[Union@@g],Select[DeleteCases[g,{_}],Function[ed,Complement[ed,#]=={}]]=={}&],Union@@g]}];
%t simpleSpans[n_]:=simpleSpans[n]=If[n==0,{{}},Union@@Table[If[#=={},Union[ine,{{n}}],Union[Complement[ine,List/@#],{#,n}&/@#]]&/@Subsets[Range[n-1]],{ine,simpleSpans[n-1]}]];
%t Table[Length[Union[chromSF/@simpleSpans[n]]],{n,6}] (* _Gus Wiseman_, Nov 21 2018 *)
%Y Cf. A000088, A000110, A000569, A006125, A229048, A240936, A245883, A277204, A277205, A321750, A321751, A321895, A321911.
%K nonn,more
%O 1,2
%A _Sam Heil_ and _Caleb Ji_, Oct 04 2016
|
