Sam Heil - cp's OEIS frontend

A289472 Number of gcds-sortable two-rooted graphs on n vertices.

0, 1, 1, 17, 113, 7729, 224689, 61562033, 7309130417, 8013328398001, 3825133597372081, 16776170217003753137, 32072986971771549318833, 562672074981014060438175409, 4304275145962667488546071527089, 302049699050029408242290021253725873

Offset: 1

Sam Heil, Jul 06 2017

nonn

This formula comes from the fact that for each possible value of the (n-2)-vertex subgraph G containing all of the non-root vertices, if G has adjacency matrix A over F_2 then there are 4^rank(A) two-rooted gcds-sortable graphs containing the non-root subgraph G. We can apply the formula from MacWilliams for the number of symmetric binary matrices with zero diagonal of each rank to get the total number of gcds-sortable graphs.

C. A. Brown, C. S. Carrillo Vazquez, R. Goswami, S. Heil, and M. Scheepers, The Sortability of Graphs and Matrices Under Context Directed Swaps
F. J. MacWilliams, Orthogonal matrices over finite fields, Amer. Math. Monthly, 76 (1969), 152-164.

Table[Sum[2^(s^2 + 3 s) (Product[(2^(n - 2 - i) - 1), {i, 0, 2 s - 1}]/Product[(2^(2 i) - 1), {i, s}]), {s, 0, Floor[n/2] - 1}], {n, 16}] (* Michael De Vlieger, Jul 30 2017 *)

a(n) = sum(s=0, n\2-1, 2^(s^2+3*s)*prod(i=0, 2*s-1, (2^(n-2-i)-1))/prod(i=1, s, 2^(2*i)-1)); \\ Michel Marcus, Jul 07 2017

a(n) = Sum_{s=0..floor(n/2)-1} 2^(s^2+3s) * (Product_{i=0..2s-1} (2^(n-2-i)-1) / Product_{i=1..s} (2^(2i)-1)).

A289483 Number of gcds-sortable two-rooted graphs on n vertices such that all vertices have even degree.

Original entry on oeis.org

0, 1, 1, 5, 29, 365, 7565, 259533, 16766541, 1695913805, 319025518925, 99428910374221, 53629954918196557, 51436455420773021005, 81633965668282476025165, 234346782219278654389392717, 1131832076434284133556933170509

Offset: 1

Sam Heil, Jul 06 2017

nonn

This formula comes from the fact that for each possible value of the (n-2)-vertex subgraph G containing all of the non-root vertices, if G has adjacency matrix A over F_2 then there are 2^rank(A) two-rooted gcds-sortable graphs with all vertices of even degree containing the non-root subgraph G. Then, we can apply the formula from MacWilliams for the number of symmetric binary matrices with zero diagonal of each rank to get the total number of gcds-sortable graphs with all vertices of even degree.

C. A. Brown, C. S. Carrillo Vazquez, R. Goswami, S. Heil, and M. Scheepers, The Sortability of Graphs and Matrices Under Context Directed Swaps
F. J. MacWilliams, Orthogonal matrices over finite fields, Amer. Math. Monthly, 76 (1969), 152-164.

Cf. A289472.

Table[Sum[2^((s^2 + 3 s)/2) * Product[(2^(n - 2 - i) - 1), {i, 0, 2 s - 1}]/Product[(2^(2 j) - 1), {j, s}], {s, 0, Floor[n/2] - 1}], {n, 2, 17}] (* Michael De Vlieger, Jul 12 2017 *)

a(n) = sum(s=0, n\2-1, 2^((s^2+3*s)/2)*prod(i=0, 2*s-1, (2^(n-2-i)-1))/prod(i=1, s, 2^(2*i)-1)); \\ Michel Marcus, Jul 07 2017

a(n) = Sum_{s=0..floor(n/2)-1} 2^((s^2+3s)/2) * (Product_{i=0..2s-1} (2^(n-2-i)-1) / Product_{i=1..s} (2^(2i)-1))

A277686 The number of nonisomorphic graphs on n vertices whose chromatic symmetric function in the p basis has a nonzero coefficient for each possible term.

Original entry on oeis.org

1, 1, 2, 5, 20, 91, 823

Offset: 1

Caleb Ji, Sam Heil, Oct 26 2016

All graphs with a Hamiltonian path are included in this count. The smallest n for which a graph with n vertices satisfies this property and does not have a Hamiltonian path is n=5.

Cf. A277686.

A277687 a(n) is the number of nonisomorphic trees on n vertices whose chromatic symmetric function in the p basis has a nonzero coefficient for each possible term.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 4, 2, 4, 2, 18, 2, 29, 5, 8, 9, 97, 7, 148, 9, 25, 20

Offset: 1

Caleb Ji, Sam Heil, Oct 26 2016

The path graph is always included in this count.

The chromatic symmetric function is defined in Stanley (1995). By theorem 2.5 of that reference we can give an equivalent definition of this sequence. Say that a forest corresponds to the partition whose parts are the sizes of the trees in the forest. Then a(n) counts the trees on n vertices for which a forest corresponding to any partition of n can be produced by deleting edges from the tree. - Peter J. Taylor, Sep 03 2021

			For n = 5 there are three trees, but a(5) = 2 because the star tree cannot be split into a tree of size 2 and a tree of size 3. - _Peter J. Taylor_, Sep 03 2021

Richard P. Stanley, A symmetric function generalization of the chromatic polynomial of a graph, Advances in Math. 111 (1995), 166-194.

Cf. A277686.

a(16)-a(22) from Peter J. Taylor, Sep 03 2021

A277203 Number of distinct chromatic symmetric functions realizable by a graph on n vertices.

Original entry on oeis.org

1, 2, 4, 11, 33, 146, 939, 10932

Offset: 1

Sam Heil and Caleb Ji, Oct 04 2016

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

			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}.
From _Gus Wiseman_, Nov 21 2018: (Start)
The a(4) = 11 chromatic symmetric functions (m is the augmented monomial symmetric function basis):
                                     m(1111)
                            m(211) + m(1111)
                           2m(211) + m(1111)
          m(22) +          2m(211) + m(1111)
                           3m(211) + m(1111)
          m(22) +          3m(211) + m(1111)
                   m(31) + 3m(211) + m(1111)
         2m(22) +          4m(211) + m(1111)
          m(22) +  m(31) + 4m(211) + m(1111)
         2m(22) + 2m(31) + 5m(211) + m(1111)
  m(4) + 3m(22) + 4m(31) + 6m(211) + m(1111)
(End)

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.

Cf. A000088, A000110, A000569, A006125, A229048, A240936, A245883, A277204, A277205, A321750, A321751, A321895, A321911.

spsu[,{}]:={{}};spsu[foo,set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@spsu[Select[foo,Complement[#,Complement[set,s]]=={}&],Complement[set,s]]]/@Cases[foo,{i,_}];
chromSF[g_]:=Sum[m[Sort[Length/@stn,Greater]],{stn,spsu[Select[Subsets[Union@@g],Select[DeleteCases[g,{_}],Function[ed,Complement[ed,#]=={}]]=={}&],Union@@g]}];
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]}]];
Table[Length[Union[chromSF/@simpleSpans[n]]],{n,6}] (* Gus Wiseman, Nov 21 2018 *)

A277204 Number of chromatic symmetric functions realizable from exactly one graph on n vertices.

Original entry on oeis.org

1, 2, 4, 11, 33, 146, 846, 9807, 229972

Offset: 1

Sam Heil and Caleb Ji, Oct 04 2016

Cf. A277203.

A277205 Number of chromatic symmetric functions realizable by exactly 2 graphs on n vertices.

Original entry on oeis.org

0, 0, 0, 0, 1, 10, 81, 907, 16111

Offset: 1

Sam Heil and Caleb Ji, Oct 04 2016

Cf. A277203, A277204.

cp's OEIS Frontend

User: Sam Heil

A289472 Number of gcds-sortable two-rooted graphs on n vertices.

Views

Author

Keywords

Comments

Links

Programs

Mathematica

PARI

Formula

A289483 Number of gcds-sortable two-rooted graphs on n vertices such that all vertices have even degree.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A277686 The number of nonisomorphic graphs on n vertices whose chromatic symmetric function in the p basis has a nonzero coefficient for each possible term.

Views

Author

Keywords

Comments

Crossrefs

A277687 a(n) is the number of nonisomorphic trees on n vertices whose chromatic symmetric function in the p basis has a nonzero coefficient for each possible term.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A277203 Number of distinct chromatic symmetric functions realizable by a graph on n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A277204 Number of chromatic symmetric functions realizable from exactly one graph on n vertices.

Views

Author

Keywords

Crossrefs

A277205 Number of chromatic symmetric functions realizable by exactly 2 graphs on n vertices.

Views

Author

Keywords

Crossrefs