This site is supported by donations to The OEIS Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A321994 Number of different chromatic symmetric functions of hypertrees on n vertices. 4
1, 1, 2, 4, 9, 22, 59, 165 (list; graph; refs; listen; history; text; internal format)



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).

Stanley conjectured that the number of distinct chromatic symmetric functions of trees with n vertices is equal to A000055, i.e., the chromatic symmetric function distinguishes between trees. It has been proven for trees with up to 25 vertices. If it is true in general, does the chromatic symmetric function also distinguish between hypertrees, meaning this sequence would be equal to A035053?


Table of n, a(n) for n=1..8.

Jeremy L. Martin, The uniqueness problem for chromatic symmetric functions of trees (2015)

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.


spsu[_, {}]:={{}}; spsu[foo_, set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]&/@spsu[Select[foo, Complement[#, Complement[set, s]]=={}&], Complement[set, s]]]/@Cases[foo, {i, ___}];

stableSets[u_, Q_]:=If[Length[u]===0, {{}}, With[{w=First[u]}, Join[stableSets[DeleteCases[u, w], Q], Prepend[#, w]&/@stableSets[DeleteCases[u, r_/; r===w||Q[r, w]||Q[w, r]], Q]]]];

csm[s_]:=With[{c=Select[Tuples[Range[Length[s]], 2], And[OrderedQ[#], UnsameQ@@#, Length[Intersection@@s[[#]]]>0]&]}, If[c=={}, s, csm[Union[Append[Delete[s, List/@c[[1]]], Union@@s[[c[[1]]]]]]]]];


hyall[n_]:=Select[stableSets[Select[Subsets[Range[n]], Length[#]>1&], Or[SubsetQ[#1, #2], Length[Intersection[#1, #2]]>1]&], And[Union@@#==Range[n], Length[csm[#]]==1, density[#]==-1]&];

chromSF[g_]:=Sum[m[Sort[Length/@stn, Greater]], {stn, spsu[Select[Subsets[Union@@g], Select[DeleteCases[g, {_}], Function[ed, Complement[ed, #]=={}]]=={}&], Union@@g]}];

Table[Length[Union[chromSF/@If[n==1, {{{1}}}, hyall[n]]]], {n, 5}]


Cf. A000055, A000569, A001187, A001349, A006125, A035053, A229048, A240936, A245883, A277203, A030019, A321750, A321895, A321911.

Sequence in context: A171367 A092920 A177377 * A035053 A000571 A077003

Adjacent sequences:  A321991 A321992 A321993 * A321995 A321996 A321997




Gus Wiseman, Nov 24 2018



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 15 16:09 EDT 2019. Contains 325049 sequences. (Running on oeis4.)