{'fraction_non_alphanumeric': 0.05368497221067541, 'fraction_numerical': 0.011269687312364326, 'mean_word_length': 3.5735811857484863, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 30, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The kernel of chromatic quasisymmetric functions on graphs and nestohedra

The chromatic symmetric function on graphs is a celebrated graph invariant. Analogue chromatic maps can be defined on other objects, as presented by Aguiar, Bergeron and Sottile. The problem of identifying the kernel of some of these maps was addressed by Féray, for the Gessel quasisymmetric function on posets. On graphs, we show that the modular relations and isomorphism relations span the kernel of the chromatic symmetric function. This helps us constructing a new invariant on graph, which may be helpful in tackling the tree conjecture. We also address the kernel problem in the Hopf algebra of generalised permutahedra, introduced by Aguar and Ardilla, and present a solution to the kernel problem on the Hopf algebra spanned by nestohedra, which is a subfamily of generalised permutahedra. Finally, we consider the non-commutative analogues of these quasisymmetric invariants in a unified way, and describe a universal property for WQSym, similar to the one in QSym, in the realm of combinatorial Hopf monoids. As a corollary, we show that there is no combinatorial Hopf monoid morphism between the combinatorial Hopf monoid of posets and the combinatorial Hopf monoid of nestohedra.


Introduction Chromatic function on graphs
For a graph G with vertex set V (G), a colouring f of the graph G is a function f : V (G) → N. A colouring is proper in G if no edge is monochromatic.
We denote by G the graph Hopf algebra, which is a vector space freely generated by the graphs whose vertex sets are of the form [n] for some n ≥ 0. This can be endowed with a Hopf algebra structure, as described by Schmitt in [Sch94], and also presented below in Section 2.2.
Stanley defines in [Sta95] the chromatic symmetric function of G in commuting variables where we write x f = v∈V (G) x f (v) , and the sum runs over proper colourings of the graph G. Note that Ψ G (G) is in the ring Sym of symmetric functions. The ring Sym is a Hopf subalgebra of QSym, the ring of quasisymmetric functions introduced by Gessel in [Ges84]. A long standing conjecture in this subject, commonly referred to as the tree conjecture, is that if two trees T 1 , T 2 are not isomorphic graphs, then Ψ G (T 1 ) = Ψ G (T 2 ). When V (G) = [n], the natural ordering on the vertices allows us to consider a non-commutative analogue of Ψ G , as done by Gebhard and Sagan in [GS01]. They define the chromatic symmetric function on non-commutative variables {a i } i≥1 as where we write a f = a f (1) . . . a f (n) , and we sum over the proper colourings f of G.
Note that Ψ G (G) is homogeneous and symmetric in the variables {a i } i≥1 . Such power series are called word symmetric functions. The ring of word symmetric functions, WSym for short, was introduced in [RS06], and is sometimes called the ring of symmetric functions in non-commutative variables.
In this paper we describe generators for ker Ψ G and ker Ψ G . A similar problem was already considered for posets. In [Fér15], Féray studies Ψ Pos , the Gessel quasisymmetric function defined on the poset Hopf algebra, and describes a set of generators of its kernel.
Some elements of the kernel of Ψ G have already been constructed in [GP13] by Guay-Paquet and independently in [OS14] by Orellana and Scott. These relations, called modular relations, extend naturally to the non-commutative case. We introduce them now.
Given a graph G and an edge set E that is disjoint from E(G), let G ∪ E denote the graph G with the edges in E added. For a graph G, if we have edges e 3 ∈ G and e 1 , e 2 ∈ G such that {e 1 , e 2 , e 3 } forms a triangle, then (2) Figure 1: Example of a modular relation.
For such a graph G, we call the formal sum G−G∪{e 1 }−G∪{e 2 }+G∪{e 1 , e 2 } in G a modular relation on graphs. An example is given in Fig. 1. Our first goal is to show that these modular relations span the kernel of the chromatic symmetric function in non-commuting variables.
Theorem 1 (Kernel and image of Ψ G : G → WSym). The modular relations span ker Ψ G . The image of Ψ G is WSym.
Two graphs G 1 , G 2 are said to be isomorphic if there is a bijection between the vertices that preserves edges. For the commutative version of the chromatic symmetric function, if two isomorphic graphs G 1 , G 2 are given, we know that Ψ G (G 1 ) and Ψ G (G 2 ) are the same. The formal sum in G given by G 1 − G 2 is called an isomorphism relation on graphs.
Theorem 2 (Kernel and image of Ψ G : G → Sym). The modular relations and the isomorphism relations generate the kernel of the commutative chromatic symmetric function Ψ G . The image of Ψ G is Sym.
The second part of this theorem is already present in previous work. For instance, in [CvW15], several bases of Sym n are constructed that come from the chromatic symmetric function of graphs, namely are of the form {Ψ G (G λ )|λ n} for suitable graphs G λ on n vertices.
In the end of Section 3 we introduce a new graph invariantΨ, called the augmented chromatic invariant. It will be easy to see that modular relations on graphs are in the kernel of the augmented chromatic invariant. It will follow from Theorem 2 that the kernel of the chromatic symmetric function in commutative variables is exactly kerΨ.
To conclude, this reduces the tree conjecture in Ψ G to this new invariantΨ, where seemingly more information can be obtained from its coefficients, and can be useful in tackling said conjecture.
Our other goal in this paper is to look to other kernel problems of chromatic flavour as well. In particular, we want to establish similar results to Theorem 1 and Theorem 2 in the combinatorial Hopf algebra of nestohedra, which is a Hopf subalgebra of generalised permutahedra that we introduce now.

Generalised Permutahedra
The family of generalised permutahedra is a family of polytopes that include permutahedra, associahedra and graph zonotopes. This family has been studied, for instance, in [PRW08], and we will introduce it now.
The Minkowsky sum of two polytopes a, b is set as a+ M b = {a+b| a ∈ a, b ∈ b}. The Minkowsky difference a − M b is defined as the unique polytope c that satisfies b + M c = a, if it exists. We denote as M i a i the Minkowsky sum of several polytopes.
If we let {e i |i ∈ I} be the canonical basis of R I , a simplex is a polytope of the form s J = s(J) = conv{e j |j ∈ J} for non-empty J ⊆ I, and a generalised permutahedron in R I is a polytope of the form A nestohedron is a generalised permutahedron where the coefficients a J in (3) are non-negative. For a nestohedron q, we denote F(q) ⊆ 2 I \ ∅ as the family of sets J ⊆ I such that a J > 0. A a primitive nestohedron on R I is a nestohedron M J⊆2 I \∅ a J s J such that a J ∈ {0, 1}. Finally, for a set A ⊆ 2 I \ ∅, we write F −1 (A) for the nestohedra q = M J∈A s J . Note that a primitive nestohedron is of the form F −1 (A) for some family A ⊆ 2 [n] \ ∅. One can easily note that the nestohedron q and F −1 (F(q)) are, in general, distinct, so some care will come with this notation. However, the face structure is the same, and we will have an explicit combinatorial equivalence in Proposition 33.
In [AA17], Aguiar and Ardila define GP, a Hopf algebra structure on the linear space generated by generalised permutahedra in R n for n ≥ 0. The Hopf subalgebra Nesto is the linear subspace generated by nestohedra.
In [Gru16], Grujić introduced a quasisymmetric map in generalised permutahedra Ψ GP : GP → QSym that we will recall now. For a polytope q ⊆ R I , Grujić defines a function f : I → N to be q-generic if the face of q that minimises i∈I f (i)x i , denoted q f , is a point. Equivalently, f is q-generic if it lies in the interior of the normal cone of some vertex.
Then, Grujić defines for a set {x i } i≥1 of commutative variables, the quasisymmetric function: This is called quasisymmetric function the chromatic quasisymmetric function on generalised permutahedra, or simply commutative chromatic quasisymmetric function.
In [AA17], Aguiar and Ardila define the graph zonotope Z : G → GP, a Hopf algebra morphism that is injective and maps Ψ G to Ψ GP . They also define other zonotone type maps from other combinatorial Hopf algebras, like matroids, to GP, that preserve the canonical Hopf algebra morphisms. For some Hopf algebras h Aguiar, Bereron and Sotille in [ABS06] are able to define its chromatic quasisymmetric function Ψ h : h → QSym, and the reader can find more details on this construction can be found below in Section 2. If we are able to describe ker Ψ GP , then such zonotone type maps Z : h → GP give us some information on ker Ψ h , since we have that Z(ker Ψ h ) = ker Ψ GP ∩ Z(h).
We discuss now a non-commutative version of Ψ GP , where we will establish an analogue of Theorem 1 to nestohedra. For that, consider the Hopf algebra of word quasisymmetric functions WQSym, a version of QSym in non-commutative variables introduced in [NT06]. For a generalised permutahedron q and noncommutative variables {a i } i≥1 , let a f = a f (1) · · · a f (n) and define We will see form Proposition 9 that Ψ GP (q) is a word quasisymmetric function. Indeed, easy computation shows that it defines a Hopf algebra morphism between GP and WQSym. Let us call Ψ Nesto and Ψ Nesto the restrictions of Ψ GP and Ψ GP to Nesto, respectively.
Our next theorems describe the kernel of the maps Ψ Nesto and Ψ Nesto , using two types of relations: • the simple relations, which are presented in Proposition 33, and convey that Ψ GP (q) only depends on which coefficients a I are positive; • the modular relations, which are exhibited in Theorem 34. These generalise the ones for graphs, in the sense that the graph zonotope embedding Z, maps modular relations on graphs to modular relations on nestohedra.
Theorem 3 (Kernel and image of of Ψ Nesto : Nesto → WQSym). The space ker Ψ Nesto is generated by the simple relations and the modular relations in nestohedra. The image of Ψ Nesto is SC, a proper subspace of WQSym introduced in Definition 26 below.
Let us denote by WQSym n the linear space of homogeneous word quasisymmetric functions of degree n, and let SC n = SC ∩ WQSym n . A monomial basis for SC is presented in Definition 26. Asymptotics for the dimension of SC n are computed in Proposition 39, where in particular it is shown that it is exponentially smaller than the dimension of WQSym n .
Two generalised permutahedra q 1 , q 2 are isomorphic if one can be obtained from the other by permuting the coordinates. If q 1 , q 2 are isomorphic, the commutative chromatic quasisymmetric functions Ψ GP (q 1 ) and Ψ GP (q 2 ) are the same. We call to q 1 − q 2 an isomorphism relation on nestohedra.
Theorem 4 (Kernel and image of Ψ Nesto : Nesto → QSym). The linear space ker Ψ Nesto is generated by the simple relations, the modular relations and the isomorphism relations. The image of Ψ Nesto is QSym.
A description of ker Ψ Nesto is less general than a description of ker Ψ GP . Nevertheless, most of the combinatorial objects embedded in GP are also in Nesto, such as graphs and matroids, so the result in the Nesto Hopf subalgebra can already be used to help us on other kernel problems.

Universal morphisms
The maps Ψ G and Ψ G arise from more general constructions in Hopf algebras and Hopf monoids, respectively. For a Hopf algebra h, a character η of h is a linear map η : h → K that preserves the multiplicative structure and the unit of h. We define a combinatorial Hopf algebra as a pair (h, η) where h is a Hopf algebra and η : h → K a character of h. For instance, the ring of quasisymmetric functions QSym is a well known Hopf algebra that has a very natural character η 0 , so (QSym, η 0 ) is a combinatorial Hopf algebra. In [ABS06], Aguiar, Bergeron, and Sotille showed that any combinatorial Hopf algebra (h, η) has a unique combinatorial Hopf algebra morphism Ψ h : h → QSym, i.e. a Hopf algebra morphism that send the character η 0 to η. Equivalently, (QSym, η 0 ) is a terminal object in the combinatorial Hopf algebras. The construction of Ψ h is given in [ABS06] and also presented below in Section 2, and we will refer to these maps as the universal maps to QSym.
The commutative invariants previously shown on graphs Ψ G , on posets Ψ Pos and on generalised permutahedra Ψ GP are Hopf algebra morphisms that can be obtained as universal maps to QSym: if we take a character η(G) = 1[G has no edges] on the graphs Hopf algebra, the unique combinatorial Hopf algebra morphism G → QSym is exactly the map Ψ G . With the Hopf algebra structure imposed on GP in [AA17], if we consider the character η(q) = 1[q is a point], then Ψ GP is the universal map from GP to QSym.
To see the maps Ψ G : G → WSym and Ψ GP : GP → WQSym as universal maps, we will draw the parallel of QSym in the realm of Hopf monoids in vector species, to which we dedicate the last chapter. The Hopf monoid WQSym is presented for instance in [AM10] as the Hopf algebra of faces. We will see that this Hopf monoid plays the role of QSym in the Hopf monoids in vector species, as it is a terminal object. Incidentally, this Hopf monoid has a structure of combinatorial Hopf monoid and for any other combinatorial Hopf monoid (h, η) there is a unique combinatorial Hopf monoid morphism Ψ h : h → WQSym. Finally, we note that by applying the so called full Fock functor to Ψ h we obtain a Hopf algebra morphism to WQSym. The maps Ψ G , Ψ GP arises applying a Fock functor to the unique combinatorial Hopf monoid morphism from the Hopf monoid on graphs G and of generalised permutahedra GP to WQSym. We will refer to these Hopf algebra morphisms as the universal maps to WQSym. If we start with the poset Hopf monoid Pos we obtain the non-commutative analogue Ψ Pos of the Gessel invariant, presented in [Fér15].
Finally, we will use the results on the SC space, in particular that it is a proper subspace of WQSym, to show that there is no combinatorial Hopf monoid morphism that maps the Hopf monoid on posets to the Hopf monoid on nestohedra.
Note: for sake of clarity, we have been using boldface for non-commutative Hopf algebras, their elements, and the associated combinatorial objects, like word symmetric functions. We will try to maintain that notational convention throughout the paper.

Preliminaries
For an equivalence relation ∼ on a set A, we call [x] ∼ to the equivalence class of x in ∼, and we write [x] when ∼ is clear from context. We write both E(∼) and A/ ∼ for the set of equivalence classes of ∼.

Linear algebra preliminaries
The following easy linear algebra lemmas will be useful to compute generators of the kernels and the images of Ψ and Ψ. These lemmas describe a sufficient condition for a set B to span the kernel of a linear map φ : V → W .
Lemma 5. Let V be a finite dimensional vector space with a basis {a i |i ∈ [m]}, φ : V → W be a linear map, and B = {b j |j ∈ J} ⊆ ker φ be a family of relations.
Assume that there exists I ⊆ [m] such that: • the elements (φ(a i )) i∈I form a linearly independent family in W , • for i ∈ [m] \ I we have a i = b + m k=i+1 λ k a k for some b ∈ B and some scalars λ k ; Then B spans ker φ. Additionally, we have that (φ(a i )) i∈I is a basis of the image of φ.
The following lemma will help us dealing with the composition Ψ = comu •Ψ: we give a sufficient condition for a natural enlargement of the set B to generate ker Ψ, given that it already generates ker Ψ. Lemma 6. We will use the same notation as in Lemma 5. Additionally, consider φ 1 : W → W linear map and call φ = φ 1 • φ. Take an equivalence relation ∼ in Assume the hypothesis in Lemma 5 and, additionally, suppose that the family Then ker φ is generated by Proof of Lemma 5. Suppose, for sake of contradiction, that there is some element c ∈ ker φ \ B . In particular c = 0. Write Note that if λ i = 0 for every i ∈ I, then which, by linear independence of (φ(a k )) k∈I , implies that λ k = 0 for every k ∈ I, contradicting c = 0 and concluding that we have λ i = 0 for some i ∈ I. Hence there is an index i c ∈ I \ I which is the smallest index in I \ I such that λ i is non-zero in (5), i.e. for j ∈ I \ I we have that By hypotheses, because i c ∈ I, there is some b ∈ B such that: So applying this to (6) gives us: Note that c − λ ic b j ∈ ker φ \ B which contradicts the maximality of i c . From this we conclude that no such c ∈ ker φ \ B exists.
Proof of Lemma 6. Define I = {max A| A ∈ E(∼)}. Note that for every j ∈ I \ I there is c ∈ C such that a j = c + m k=j+1 λ k a k . Indeed it is enough to choose i ∼ j with i > j and write a j = a j − a i ∈C +a i .
So the set I ⊆ I satisfies both: • We have that (φ (a i )) i∈I = (φ ([a i ])) i∈I is linearly independent in W ; • For i ∈ I \ I we can write a i = b + m k=j+1 λ k a k for some b ∈ B ∪ C and some scalars λ k . Now applying Lemma 5 to I instead of I, to φ instead of φ and to B ∪ C instead of B tells us that B ∪ C generates ker φ , and {φ ([a i ])|i ∈ I} = {φ (a i )|i ∈ I} spans the image of φ , as desired.

Hopf algebras and associated combinatorial objects
In the following, all the Hopf algebras H have a grading, denoted as H = ⊕ n≥0 H n .
An integer composition, or simply a composition, of n, is a list α = (α 1 , · · · , α k ) of positive integers which sum is n. We write α |= n. We denote l(α) for the length of the list and we denote as C n the set of compositions of size n.
An integer partition, or simply a partition, of n, is a non-increasing list of positive integers λ = (λ 1 , · · · , λ k ) which sum is n. We denote λ n. We write l(λ) for the length of the list and we denote as P n the set of partitions of size n. By disregarding the order of the parts on a composition α we obtain a partition λ(α).
A set partition π = {π 1 , · · · , π k } of a set I is a collection of non-empty disjoint subsets of I, called blocks, that cover I. We write π I. We denote l(π), or length, for the number of parts of the set partition. We write P I for the family of set partitions of I, or simply P n if I = [n]. By counting the elements on each block we obtain an integer partition denoted λ(π) #I. We identify a set partition π ∈ P I with an equivalence relation ∼ π on I, where x ∼ π y if x, y ∈ I are on the same block of π.
A set composition π = S 1 | · · · |S l of I is a list of non-empty disjoint subsets of I that cover I. We write π |= I. We denote l( π) for the size of the set composition. We call C I to the family of set compositions of I, or simply C n if I = [n]. By disregarding the order of a set composition π, we obtain a set partition λ( π) I. By counting the elements on each block we obtain a composition denoted α( π) |= #I. A set composition is naturally identified with a total preorder R π on I, where xR π y if x ∈ S i , y ∈ S j for i ≤ j.
A colouring of the set I is a function f : I → N. The set composition type π(f ) of a colouring f : I → N is the set composition obtained after deleting the empty We recall that in partitions and in set partitions, we define the classical coarsening orders ≤ with the same notation, where we say that π ≤ τ (resp. π ≤ τ ) if τ is obtained from π by adding some parts of the original parts together (resp. if τ is obtained from π by merging some blocks).

Hopf algebras on graphs and posets
Of interest will also be the Hopf algebra on graphs G and on posets Pos, which are graded connected, and the homogeneous component G n , resp. Pos n , are the linear span of the graphs with vertex set [n], resp. posets in the set [n].
In these graded vector spaces, we will introduce the products and coproducts in the basis elements. For that, let rl A,B be the canonical relabelling of combinatorial objects on A to combinatorial objects on B, where A, B are sets of integers with the same cardinality, and the relabelling preserves the order.
Recall that the disjoint union of graphs (  For posets, consider two posets P 1 = (S 1 , R P 1 ), P 2 = (S 2 , R P 2 ), where R represents the set of pairs (x, y) such that xleqy in the respective poset. The disjoint union of posets is written P 1 P 2 and defined as (S 1 S 2 , R P 1 R P 2 ), and the restriction of a poset P = (S, R P ) is written P | I and defined as (I, R P ∩ I × I).
Recall that S is an ideal of P if whenever x ≤ y and x ∈ S, then y ∈ S. Define the product P · Q = P rl [n],[n+1,n+m] (Q) .
And the coproduct These operations indeed define a Hopf algebra structure in G and Pos.

Faces and a Hopf algebra structure of generalised permutahedra
In the cartesian space R I for I finite set, we set s J = conv{e v | v ∈ J} for the simplex on J ⊆ I. Recall that a generalised permutahedra is a Minkowsky sum of the form for reals L(q) = {a J } ∅ =J⊆I that can be either positive, negative or zero.
Recall as well that a nestohedra is a generalised permutahedra of the form For a polytope q, a face is the solution to a linear optimisation problem on q. If we take a colouring f on I, we abbreviate the face that solves the linear optimisation problem on f as In particular, note that if J 1 ⊆ J 2 , then s(J 1 ) is a face of s(J 2 ) corresponding to any colouring f that is constant and minimal exactly in J 1 . The following fact is a widely known behaviour of the Minkovsky sum towards linear optimisation problems: Lemma 8. Let f be a colouring and a, b two polytopes.
For a set composition π on [n] and a non-empty set J ⊆ [n], we define the set J π = {minima of J in R π }. Then, for a colouring f : [n] → N note that the face corresponding to f of a simplex are easily computed as: As a consequence of Lemma 8, the face that minimises the linear optimisation problem on f of a generalised permutahedron is then given by in particular, the face of a generalised permutahedron q f only depends on the set composition type of the colouring f . We will denote by q π the face on q that solves any linear optimisation problem on a colouring f that satisfies π(f ) = π. We have immediately the following: Proposition 9. If q is a generalised permutahedra, then Note that if π = A|B is a set composition, then q π can be written as a cartesian product (or as a Minkowsky sum of polytopes in orthogonal spaces) so that where q| A is a generalised permutahedra in R A × {0} B and q\ A is a generalised permutahedra on R B ×{0} A . These will be identified with generalised permutahedra in R A and R B without further notice. Note that B = A c so the dependence of q| A and q\ A on B is implicit.
then we can obtain explicit expressions for q| A and q\ A : We have now all the material to endow the generalised permutahedra with a Hopf algebra structure according to [AA17]: let GP = ⊕ n≥0 GP n , where GP n is the free linear space on generalised permutahedra in R n .
The GP linear space has the following product, when q 1 , q 2 are generalised permutahedra in R n , R m respectively: The GP linear space has the following coproduct, when q is a generalised permutahedra in R n :

Chromatic functions on Hopf algebras
In [ABS06], a character η on a graded Hopf algebra h over the field K is an algebra morphism η : h → K, i.e. a linear map that preserves multiplication and unit. Pairs (h, η) are called combinatorial Hopf algebras, and it was shown in [ABS06] that there is a unique Hopf algebra morphism that maps η 0 to η. This morphism is denoted as Ψ h : h → QSym and it was also constructed by Aguiar, Bergeron and Sottile. We point out that the abuse of notation between the unique Hopf algebra morphisms and the chromatic functions previously introduced for graphs, posets and generalised permutahedra is not innocent. In fact, these chromatic functions can easily be seen to be Hopf algebra morphisms, and for suitable characters, by uniqueness, these maps correspond to the construction of [ABS06].
Example 10. We define the following characters on the graph Hopf algebra, on the poset Hopf algebra and on the Hopf algebra of generalised permutahedra: for a graph G, let η G (G) = 1[G has no edges], for a poset P , define the character η Pos (P ) = 1[P is an antichain] and for a generalised permutahedra q define the character η(q) = 1[q is a point].
Consequently, by [ABS06], they are the unique combinatorial Hopf algebras from QSym to G, Pos and GP.
The construction of the unique combinatorial Hopf algebra morphism is as follows: For a composition α |= n of length l, we define the natural projection π α : h ⊗l → h α 1 ⊗ · · · ⊗ h α l which is the tensor of all canonical projections h into the subspace h α i . Define then and the following defines a Hopf algebra morphism, for a ∈ h n : When the Hopf algebras come from Hopf monoids in vector species, which is the case in the examples presented so far, and when the characters are zero-one functions on the basis elements, then equations of the following type arise naturally: where we define η f (a) = 1[f is proper in a], for some suited notion of properness. We will observe here explicitly that the chromatic functions and the unique Hopf algebra morphisms are the same directly by the construction and without using the uniqueness.
Example 12 (Graphs and generalised permutahedra). In graphs we recall that a colouring f is proper in G if f is not monochromatic in any edge of G. Note that η α (G) is the number of set compositions of type α that are stable, i.e. that no two vertices in the same block are adjacent. Hence, we can explicitly see that the previous definitions of Ψ G all coincide: where the sum runs over all compositions of n.
Similarly, for generalised permutahedra, we say that a colouring f is proper in q, or that it is q-generic, if q f is a vertex of q. Indeed, in this case, one can see that (10) holds.
In what follows, we will use the notation of a multicharacter, which is given by η f (a) := 1[f proper colouring on a] whenever a notion of properness exists, and extend linearly so that it is a map from h. Now, we talk about the non-commutative analogues of the quasisymmetric functions. This generalisation is automatic when our Hopf algebra comes from a Hopf monoid, and consequentially when η f (a) depends only on the set composition type of f . We will see this generalisation as a Hopf monoid morphism in Section 5.
Definition 13. For graphs, Gebhard introduced in [GS01] the following word symmetric function: For generalised permutahedra the following is a consequence of (9): where η π (q) = 1[q π is a vertex of q].

Main theorems on graphs
In this section we will prove Theorem 1 and Theorem 2, which will be applications of Lemma 5 and Lemma 6. We discuss as well an application of Theorem 2 on the tree conjecture, by constructing a new graph invariantΨ(G) that satisfies the modular relations. We now recall the monomial expansion of chromatic symmetric functions: . For a graph G we say that a set partition τ of V (G) is proper if no block of τ contains an edge. Then have that where the sum runs over all proper set partitions of V (G).
For a set partition π, we define the graph K π where {i, j} ∈ E(K π ) if i ∼ π j. This graph is the disjoint union of the complete graphs on the blocks of π. We denote the complement of K π as K c π . Note that a set partition τ is proper in K c π if and only if τ ≤ π in the coarsening order on set partitions. Hence, as a consequence of Lemma 14, We now show that the kernel of Ψ G is spanned by the modular relations.
Proof of Theorem 1. Recall that G n is spanned by graphs with vertex set [n]. We choose an order≥ in this family of graphs in a way that the number of edges is non-decreasing.
From (14), we know that the transition matrix of {Ψ G (K c π )|π ∈ P n } over the monomial basis of WSym is upper triangular, hence forms a basis set of WSym. In particular, im Ψ G = WSym.
In order to apply Lemma 5 to the set of modular relations on graphs, it suffices to show the following: if a graph G is not of the form K c π , then we can find a formal sum G − G ∪ {e 1 } − G ∪ {e 2 } + G ∪ {e 1 , e 2 } that is a modular relation. Indeed, G is the graph with least edges in that expression, so it is the smallest in the order≥. If the above holds, Lemma 5 implies that the modular relations generate the space ker Ψ G .
To find the desired modular relation, it is enough to find a triangle {e 1 , e 2 , e 3 } such that e 1 , e 2 ∈ E(G) and e 3 ∈ E(G). Consider τ , the set partition given by the connected components of G c . By hypothesis, G = K c τ , so there are vertices v, w in the same block of τ that are not neighbours in G c . Without loss of generality we can take such u, w that are at distance 2 in G c , so they have a common neighbour v in G c (see example in Fig. 2). Proof of Theorem 2. It is clear that Ψ G is surjective, since Ψ G is surjective. Now, our goal is to apply Lemma 6 to the map Ψ G = comu •Ψ G and the equivalence relation corresponding to graph isomorphism. First, note that if λ(π) = λ(τ ) then K c π and K c τ are isomorphic graphs. Define without ambiguity r λ(π) = Ψ G (K c π ). From the proof of Theorem 1, the hypothesis of Lemma 5 are satisfied. Therefore, to apply Lemma 6 it is enough to establish that the family (r λ ) λ∈Pn is linearly independent. Indeed, it would follow that ker Ψ G is generated by the modular relations and the isomorphism relations, and (r λ ) λ∈Pn is a basis of im Ψ G concluding the proof.
Remark 15. We have obtained in the proof of Theorem 2 that (r λ ) λ n is a basis for Sym n . This basis is different from other "chromatic bases" proposed in [CvW15].
The proof gives us a recursive way to compute the coefficients ζ λ on the span Ψ G (G) = λ ζ λ r λ . It is then natural to ask if combinatorial properties can be obtained for these coefficients, which are isomorphic invariants. Similarly in the non-commutative case, we obtain that WSym n is spanned by , and so other coefficients arise. We can again ask for combinatorial properties of these coefficients.

The augmented chromatic invariant
Consider the ring of power series K[[x 1 , x 2 , . . . ; q 1 , q 2 , . . . ]] on two countable collections of commuting variables, and let R be such ring modulo the relations Note that we can simplify further with q 3 i = 2q 2 i − q i . The main property of this graph invariant is that its kernel is ker Ψ G , as it will be shown latter, using Theorem 2: Proposition 16. We have that kerΨ = ker Ψ G . In particular, for graphs Take, for instance, the celebrated tree conjecture introduced in [Sta95]: Conjecture 17 (Tree conjecture on chromatic symmetric functions). If two trees Consequently, from Proposition 16, the tree conjecture is equivalent to the following conjecture: Conjecture 18. If two trees T 1 , T 2 are not isomorphic, thenΨ(T 1 ) =Ψ(T 2 ).
One strategy that has been employed to show that two non-isomorphic trees have different chromatic symmetric function is to construct said trees using its coefficients over several bases, see for instance [OS14], [SST15] and [APZ14]. One can observe thatΨ provides more coefficients to reconstruct a tree, so employing the same strategy to prove Conjecture 18 is promising.
Proof of Proposition 16. Note that we haveΨ(G)| q i =0 ∀i≥1 = Ψ G (G). This readily yields kerΨ ⊆ ker Ψ G . To show that kerΨ ⊇ ker Ψ G , we need only to show that the modular relations and the isomorphism relations belong to kerΨ. for the isomorphism relations, this is trivial.
For a colouring f on a graph H and a monochromatic edge e in H, define c(e) the colour of the vertices of e. Abbreviate 1[e is monochromatic] = m(e). Note that we have Set • None of the edges e 1 , e 2 is monochromatic. Then, the contribution of monochromatic edges to c H (f, i) in (15) comes only from edges in G, and then grouping the common factors yields: c(e) (1 − 1 − 1 + 1) = 0 • The edge e 1 is monochromatic of colour a, and f (v 1 ) = b = a. Then, again grouping the common factors in (15) gives: c(e) (1 − q a − 1 + q a ) = 0 • The edge e 2 is monochromatic of colour a, and f (v 2 ) = b = a. Then, Then, in the ring R we immediately have In conclusion, any modualr relation and any isomorphism relation is in kerΨ. From Theorem 2 we have that ker Ψ G ⊆ kerΨ, so we conclude the proof.
We will now do as follows: we consider some specializations ofΨ and obtain back a linear combination of chromatic symmetric function of smaller graphs, in Theorem 19. The main goal with the rest of this section is to explore how it might be possible to obtain Proposition 16 without using Theorem 1. We should clarify that we do not have a complete proof, and this illustrates the strength of the kernel approach. Let us first set up some necessary notation.
For an element f ∈ R, denote f q i =a the specialisation of the variable q i to a in f , whenever defined (for a = 0 or a = 1). Additionally, denote by f q i =1 the specialisation of the variable q i to 1 in ∂ ∂q i f by 1. We also use this for the x i variables, and specialise infinitely many variables to zero, which should be understood as the natural limit object. We note that, in general, taking infinitely many specialisation of the form q i = 1 is not allowed, as the reader can readily check. Taking specialisations of q i to a ∈ {0, 1, 1 } is not well defined in the quotient ring, so it is also not allowed.
For an edge e ∈ E(G), let us denote G \ e as the graph resulting after both endpoints of e are deleted from G, along with all incident edges.
We say that a tuple of edges m = (e 1 , . . . , e j ) is an ordered matching if no two edges share a vertex, and call M k (G) the set of ordered matchings of size k on a graph G. We write G \ m for (G \ e 1 ) \ · · · \ e j , which of course does not depend on the order of the matching.
Finally, for a symmetric function f over the variables x 1 , x 2 , . . . , let f ↑ k be the symmetric function over the variables x k+1 , x k+2 , . . . with each index in f shifted up by k.
We will obtain now a formula forΨ(G) that depends only on some Ψ G (H i ), where each H i is a graph with less vertices than G.
Theorem 19. Let k ≥ 0. We have the following relation between the graph invari-antΨ and the original chromatic symmetric function Ψ G : Proof. First observe that Say that a colouring is k-proper if all monochromatic edges have colour j ≤ k. Then, it is clear that m=(e 1 ,...,e k ) g colouring in G\m g is k -proper in G\m Where we note that, for a fixed colouring f , k i=1 c G (i, f ) counts ordered matchings (e 1 , . . . , e k ) in G with f (e i ) = {i}.
So after the specialization x i = 0 for i = 1, . . . , k, all colourings of G \ m that use a colour j ≤ k vanish, sõ as desired.
The general strategy now is as follows: we wish to use the coefficients of Ψ G (G) to determine the right hand side of Theorem 19, and use the left hand side to determineΨ(G). It would readily follow that Ψ G (G) determinesΨ(G), i.e. we would prove Proposition 16 without using Theorem 1.
The following proposition has a good synergy with this strategy, as it accomplishes exactly the first task.
Proposition 20. If G 1 , G 2 are two graphs such that Ψ G (G 1 ) = Ψ G (G 2 ), and k a positive number, then Proof. We will use the power-sum basis {p λ } λ n of Sym n introduced, for instance, in [Sta86].
It suffices to show that, for a generic graph H the coefficients in the expression m∈M k (H) Ψ G (H \ m) in the power-sum basis are a function of the coefficients of Ψ G (H) in the power-sum basis. Once this is established, the proposition follows.
For a graph G and a set of edges S ⊆ E(S), write c(S) for the number partition of the underlying set partition of connected components generated by the edge set S. In [Sta95] the following expression for the coefficients in the power-sum basis is shown: Suppose that Ψ G (H) = λ n c λ p λ . For a number partition λ write λ (2) for the number of parts of size two, and define λ ∪ (2 k ) as the partition with k extra parts of size two. Then we have that Reorder the sum with respect to R = S ∪ m, and note that for each R ⊆ E(H) such that λ(R) = λ ∪ (2 k ), there are exactly λ (2) +k k k! pairs (S, m) of m ∈ M k (H) and S ⊆ E(H) such that S ∪ m = R, λ(S) = λ and S ⊆ E(H \m). Hence: Therefore, the sum m∈M k (H) Ψ G (H \ m) is determined by Ψ G (H).

It follows from Theorem 19 and Proposition 20 that:
Corollary 21. If G 1 , G 2 are graphs such that Ψ G (G 1 ) = Ψ G (G 2 ), then for every integer k ≥ 0 we have: Note the following trivial fact: Proposition 22. Suppose that f 1 , f 2 ∈ R are such that for every pair of finite disjoint sets I, J ⊆ N we have In conclusion, to get an alternative proof of Proposition 16 we need to establish a generalisation of Corollary 21 that introduces specialisations of the type q i = 1, in order to apply Proposition 22. Such a generalisation has not been found by the author.

Poset structures on compositions
In this chapter we consider generalised permutahedra and nestohedra in R n , and colourings on [n]. Recall that with a set composition π ∈ C n we have the associated total preorder P π , and for a non-empty set A ⊆ [n], recall that we define the set A π = {minima of A in P π }. We say that A π = pt if A π is a singleton.
Finally, recall as well that, for a nestohedron q, we denote F(q) ⊆ 2 I \ ∅ as the family of sets J ⊆ I such that the coefficients in (3) satisfy a J > 0, and for a set Remark 23. We write a = pt whenever a is a point polytope or a singleton. This abuse of notation is justified in view of s(J) = pt ⇔ J = pt, for any set J ⊆ [n].
The following lemma is well known in the folklore of generalised permutahedra, and is shown in the discussion leading to Proposition 9.
Lemma 24 (Face characterization). Let q be a generalised permutahedra, and f a colouring. Then, the face q f that minimizes i f (i)x i only depends on the set composition π(f ).
Note that this directly implies that Ψ GP (q) ∈ QSym and Ψ GP (q) ∈ WQSym. For nestohedra, we will present a description of the faces, in Lemma 28.
Definition 25 (Fundamental nestohedra and a preorder in set compositions). For a generalised permutahedra q, we write q π for the face q f where f : [n] → N is a colouring of set composition type π, without ambiguity. For π ∈ C n , we define the fundamental nestohedron as p π = s{A ⊆ [n] |A π = pt, A = ∅}.
Additionally, we define the equivalence relation ∼ in C n as π ∼ τ whenever p π = p τ . Note that π ∼ τ is equivalent to A π = pt ⇔ A τ = pt. We write [ π] for the equivalence class of π under ∼. Then A π = pt depends only on the equivalence class of π.
By definition, it is clear that p π only depends on the equivalence class of π. We write p [ π] = p π without ambiguity.
In Theorem 3, we show that SC is the image of Ψ Nesto . We will see, as a consequence of Theorem 3, that SC is a Hopf algebra.
The following proposition gives us a way to describe the equivalence classes of ∼ in a combinatorial way, and motivates the name for , ∼ and SC. It also tells us that the map λ : C n → P n flips the SC preorder with respect to the coarsening order ≤ in P n .
Additionally, π ∼ τ if and only if all the following happens: 1. We have π = τ and; 2. Each a, b ∈ [n] that satisfies both a P π b and b P τ a are either singletons or in the same block in π.
Property 2. will be called the SC property.
Proof of Proposition 27. Suppose that π τ and take i, j elements of [n] such that i ∼ τ j. Then {i, j} ∈ F(p τ ) ⊇ F(p π ). This implies that {i, j} π = pt, hence {i, j} π = {i, j}. So we have i ∼ π j, and since i, j are generic, we have that π ≥ τ . This concludes the first part.
For the second part, we will first show the direct implication. Suppose that p π = p τ , so it follows from the first part of the proposition that π = τ . Our goal is to show the SC property.
Take a, b that are in distinct blocks in π, such that both a P π b and b P τ a. For sake of contradiction let c = a be such that c ∼ π a. Then {a, b, c} π = {a, c} = pt, but since π ∼ τ by hypothesis, we have that {a, b, c} τ = {b} = pt, which is a contradiction. This contradicts the assumption that a ∼ π c, so we conclude that a is a singleton in π. Similarly we obtain that b is also a singleton in τ = π. This shows the SC property.
For the reverse implication, suppose that π, τ are such that π = τ that satisfy the SC property. Our goal is to show that π ∼ τ , so it is enough to show that A π = pt ⇔ A τ = pt for any non empty A ⊆ [n]. Take some nonempty set A ⊆ [n] such that A π = {a} is a singleton, but A τ = pt, for sake of contradiction. Finally, take an element b ∈ A τ .
Observe that, since π = τ , either A π = A τ or A π ∩ A τ = ∅. Since, A π = A τ , they are disjoint and a = b. Note that we have a P π b, b P τ a. So, by the SC property we conclude that b is a singleton in τ , contradicting that A τ = pt.
That A τ = pt ⇒ A π = pt follows similarly, concluding the proof. Now that we have a nice characterisation of , we turn to the description of the faces of nestohedra: Lemma 28 (Vertex normal cone characterization). Let q be a nestohedron and suppose that F(q) = {A (i) |i ∈ I}. Let f be a colouring.
Then, we have that q f = pt if and only if A (i) π(f ) = pt for each i ∈ I. In particular, if π(f 1 ) ∼ π(f 2 ) then q f 1 = pt ⇔ q f 2 = pt.
Proof. By definition, if F(q) = {A (i) |i ∈ I}, then q = M i∈I a i s(A (i) ) for some coefficients a i > 0. Computing the face on both sides that minimizes f , we obtain that q f = pt if and only if  The following corollary is immediate from (13) and Lemma 28.
Corollary 29. The image of Ψ Nesto is contained in the SC space, i.e. for any nestohedra q we have that Ψ Nesto (q) ∈ SC .
Another consequence of Lemma 28 is that we have p π τ = pt precisely when A π = pt ⇒ A τ = pt, i.e. when π τ . It follow from (13) that: As presented, (21) seems to shows that the (monomial) transition matrix of (Ψ GP (p π )) π∈Cn over the monomial basis is upper triangular. Since is not an order, that is not the case, but we obtain a related result with this reasoning: Lemma 30. The family (Ψ(p [ π] )) [ π]∈Cn/∼ forms a basis of SC. In particular, we have im Ψ Nesto = SC.
Proof of Lemma 30. From (21) we have the following triangularity relation: where the preorder projects naturally into an order in C n / ∼.
∈Cn/∼ is another basis of SC. From Corollary 29, we conclude that im Ψ Nesto = SC.
In projecting to the commutative case, we wish to carry the triangularity of the monomial transition matrix in (22) into a new smaller basis in QSym, which also has an upper triangular over the transition matrix.
For that, we project the order into an order ≤ in C n as follows: we say that α ≤ β if we can find set compositions π, τ that satisfy π τ and also α( π) = α, α( τ ) = β. We will see that this projection is akin to the projection of the coarsening order of set partitions to the coarsening order on partitions. In particular, it preserves the desired upper triangularity.
However, we can also project the preorder in a stronger way: we say that α ≤ β if for every π such that α( π) = α there exists τ such that α( τ ) = β and π τ . One can see that the relations ≤ and ≤ are, in fact, the same. This fact is, however, not useful to us.
Proof. We only need to check that ≤ as defined is indeed an order.

The kernel and image problem on Nestohedra
Take a nestohedron q = M J a J s J . Recall that for a nestohedron q, we denote F(q) ⊆ 2 I \ ∅ as the family of sets J ⊆ I such that a J > 0. We also denote Recall that a primitive nestohedron on R I is a nestohedron In the following proposition, we reduce the problem of describing the kernel of Ψ Nesto to the subspace of Nesto spanned by the primitive nestohedra. We have: Remains now to discuss the kernel of the map Ψ Nesto when restricted to the span of the nestohedra {F −1 (A)|A ⊆ 2 [n] \ ∅}. For non-empty sets A ⊆ [n], we define Orth A = { π ∈ C n |A π = pt}. The following modular relations are obtained as a consequence of Lemma 28.
Theorem 34 (Modular relations for Ψ Nesto ). Let {A k |k ∈ K} and {B j |j ∈ J} be two disjoint families of non-empty subsets of [n]. Take the following families of set compositions: K = ∪ k∈K (Orth A k ) c , and J = ∪ j∈J Orth B j . Consider the nestohedron q = s{A k |k ∈ K}.
Suppose that K ∪ J = C n . Then, Proof of Theorem 34. Recall that we write η f (q) = 1[f is q − generic ]. Recall as well the expansion for general nestohedra q given by and write, for short, the modular relation for nestohedra as Hence: We note from Lemma 28 that for nestohedra q, p, if a colouring f is not qgeneric, then f is not (q + p)-generic. Hence, if η f (q) = 0 then it follows that It suffices to show that no colouring f is both q-generic and satisfies B(f ) = ∅. Suppose otherwise, and take such f . If f is q-generic, we have π(f ) ∈ K. If B(f ) = ∅ we have that π(f ) ∈ OrthB j for any j, hence π(f ) ∈ J . Given that f ∈ K ∪ J = C n , we have a contradiction.
Remark 35. It can be noted that, if l = G − G ∪ {e 1 } − G ∪ {e 2 } + G ∪ {e 1 , e 2 } is a modular relation on graphs, then the graph zonotope Z(l) is the modular relation on nestohedra corresponding to q = Z(G) ( i.e. {A k |k ∈ K} = E(G)), B 1 = e 1 and B 2 = e 2 . In this case, the condition K ∪ J = C n follows from the fact that no proper colouring of G is monochromatic in both e 1 and e 2 , which is imposed by e 3 ∈ G.
Recall that we set p π = F −1 {A ⊆ [n]|A π = pt}, which only depends on the equivalence class [ π] under ∼, and we denote simply p [ π] . These are called fundamental nestohedra and are a special case of primitive nestohedra.
What we do now is the proof of Theorem 3. We follow here roughly the same idea as in the graph case: We use the family of nestohedra (p [ π] ) [ π]∈Cn/∼ to apply Lemma 5, whose image by Ψ GP is linearly independent and is rich enough to span the image.
Proof of Theorem 3. First recall that Nesto n is a linear space generated by the nestohedra in R n and, according to Proposition 33, to compute the kernel of Ψ Nesto , it suffices us study the span of the primitive nestohedra.We choose a total order≥ on primitive nestohedra q so that #F(q) is non decreasing.
We will apply Lemma 5 with Theorem 34 to this subspace of Nesto n . Lemma 30 guarantees that (Ψ GP (p [ π] )) [ π]∈Cn/∼ is linearly independent. Therefore, it suffices to show that for any primitive nestohedra q that is not a fundamental nestohedron, we can write some modular relation b as Indeed, it would follow from Lemma 5 that the simple relations and the modular relations on nestohedra span ker Ψ Nesto . As a consequence, im Ψ Nesto is spanned by the sets {Ψ Nesto (p [ π] )|[ π] ∈ C n / ∼} for each n ≥ 0. From Lemma 30, this image is SC n .
To obtain the desired modular relation, take both {A ⊆ 2 [n] |A ∈ F(q)} and {B ⊆ 2 [n] |B ∈ F(q)} and apply Theorem 34. Let us write K = ∪ A∈F (q) (Orth A) c and J = ∪ B∈2 [n] \F (q)∪∅ Orth B. We will first show that we have K ∪ J = C n .
Take, for sake of contradiction, some π ∈ K ∪ J . Note that π ∈ K is equivalent to A π = pt for every A ∈ F(q). Note as well that π ∈ J is equivalent to B π = pt for every B ∈ F(q). Therefore, if π ∈ K ∪ J , then q = p π , contradicting the assumption that q is not a fundamental nestohedron. We obtain that K ∪ J = C n . Finally, note that is a modular relation of the desired form, showing that the hypothesis of Lemma 5 are satisfied.
It also follows from Lemma 5 that im Ψ Nesto is spanned by the linear independent word quasisymmetric functions {N [ π] : [ π] ∈ n≥0 C n / ∼}. Since SC is the image of a bialgebra morphism from Theorem 3, it is a connected graded bialgebra, hence it is a Hopf algebra.
Remark 36. Note that the span of the primitive nestohedra does not form a Hopf algebra, as it is not stable for the coproduct in generalised permutahedra.
For the commutative case we will apply Lemma 6. Note that we already have a generator set of ker Ψ Nesto , so similarly to the proof of Theorem 2, we just need to establish some linear independence.
Recall that two nestohedra q 1 and q 2 are isomorphic if there is a permutation matrix P such that x ∈ q 2 ⇔ P x ∈ q 1 . Since we are in the commutative case now, if π 1 and π 2 share the same composition type, then p π 1 and p π 2 are isomorphic, and so we have Ψ Nesto (p π 1 ) = Ψ Nesto (p π 2 ). Set R α( π) := Ψ Nesto (p π ) without ambiguity.
Proof of Theorem 4. We will apply Lemma 6 to the map Ψ Nesto = comu •Ψ Nesto on the equivalence relation corresponding to the isomorphism of nestohedra.
From the proof of Theorem 3, to apply Lemma 6 it is enough to establish that the family (R α ) α∈Cn is linearly independent. It would follow that ker Ψ Nesto is generated by the modular relations and the isomorphism relations, and (R α ) α∈Cn is a basis of im Ψ G , concluding the proof.
To show the linear independence of (R α ) α∈Cn , we write R α on the monomial basis of QSym, and use the order ≤ mentioned in Lemma 31.
Remark 37. We have obtained in the proof of Theorem 4 that (R α ) α|=n is a basis for Qym n . The proof gives us a recursive way to compute the coefficients ζ α on the span Ψ Nesto (q) = α|=n ζ α R α . It is then natural to ask if combinatorial properties can be obtained for these coefficients, which are isomorphic invariants. Similarly, in the non-commutative case, we can write the chromatic quasisymmetric function of a nestohedron as and ask for the combinatorial meaning of the coefficients (ζ [ π] ) [ π]∈Cn/∼ .

The dimension of SC space
Let sc n := dim SC n . The goal of this section is to compute the asymptotics of sc n , by using the combinatorial interpretation provided in Proposition 27.
Recall that, from Theorem 3, the SC Hopf algebra is spanned by the sums where a π 1 = a π 2 whenever π 1 ∼ π 2 in the SC equivalence relation. Hence sc n counts the equivalence classes of ∼.
Proposition 38. Let F (x) = n≥0 sc n x n n! be the exponential power series of the dimension of SC n . Then Proposition 39. The dimension of the image of Ψ Nesto , sc n , has an asymptotic growth of where δ < 1 is some real number, γ 0.814097 is the unique positive root of the equation e 2x = 1 + (1 + x)e x , and τ = Res γ (F ) 0.588175.
In particular, dim SC n is exponentially smaller than dim WQSym n = #C n .

We will prove both propositions below. A bared set composition of [n] is a set composition of [n]
where we put some bars over some of the blocks. For instance, 13|45|2 and 12|4|35 are bared set compositions of {1, 2, 3, 4, 5}.
A bared set composition is integral, or IBSC, if • No two bared blocks occur consecutively; • Every block of size one is bared; What follows are the integral bared set compositions of small size:  Proof of Proposition 38. We will use the framework developed in [FS09] of labelled combinatorial classes. In the following, calligraphic style letter will denote classes, and the associate upper case letter denotes its exponential power series. Let B be the collection {1, 12, · · · } and U = {12, 123, 1234, · · · }, with exponential power series B(x) = e x − 1 and Let F be the class of IBSC. Our goal is to show that F (x) = e x 1+(1+x)e x −e 2x . Let us as well denote F o by the class of IBSC that start with an unbarred set, and let F be the class of IBSC that start with a barred set. Note the decomposition We can recursively describe F and F o as F = B × (F o O) and F o = U × F According to the dictionary rules in [FS09], this implies The unique solution has F o (x) = e 2x −(1+x)e x 1−1e 2x +(x+1)e x which implies that as desired.
With this we can easily compute the dimension of SC n for small n.  Proof of Proposition 39. We will find the dominant singularity of F (x) and show that it is the unique positive real root of a real function, so that we can find this singularity through numerical methods quite easily.
Let l(x) := e 2x − (1 + x)e x − 1, then F (x) = − e x l(x) is the quotient of two entire functions, and the poles are the zeroes of l(x). Note that F (x) is a counting exponential power series around zero, so it has positive coefficients. By Pringsheim's Theorem as in [FS09], one of the dominant singularities of F (x) is a positive real number, call it γ.
We will see now that any other singularity z = γ of F , which is a zero of l, has to satisfy |z| > |γ|, thus showing that γ is the unique dominant singularity and allowing us to compute a simple asymptotic formula. Suppose, that z is a singularity of F distinct from γ, such that |z| = |γ|. So, we have that l(z) = 0 and that z ∈ R + . This will allow us to use a triangular inequality in its strict form, contradicting l(z) = 0. Indeed, the equation l(z) = 0 can easily be rewritten as Note that 2 n ≥ n + 1 for n ≥ 1. Now we apply the strict triangular inequality on the left hand side to obtain 1 < n≥1 |z| n 2 n − n − 1 n! = n≥1 γ n 2 n − n − 1 n! = l(γ) + 1 = 1 , a contradiction, as desired.
We additionally see that γ is the unique positive real root, so we can easily approximate it by some numerical method, for instance the bisection method: the function l in the positive real line satisfies lim x→+∞ l(x) = +∞ and l(0) = −1, so it has at least one zero. Note that such zero is unique, as l (x) > 0 for x positive. Also, since l (γ) > 0, the zero γ is simple.
Since the function F (x) is analytic around 0 in the open circle of radius γ, and γ is the dominant singularity, we conclude that for any δ such that 1 > δ > |γ/γ 2 |, where γ 2 is a second dominant singularity of F , if it exists, and arbitrarily large otherwise. We can easily approximate γ 0.814097. We can also estimate the residue of F (x) at γ as τ = Res γ (F ) = e γ l (γ) 0.588175. This proves the desired asymptotic formula.

Hopf species and the non-commutative universal property
In [ABS06], a character in a Hopf algebra is defined as a multiplicative linear map that preserves unit, and a combinatorial Hopf algebra (or CHA, for short) is a Hopf algebra endowed with a character. For instance, a character η 0 in QSym is η 0 (M α ) = 1[l(α) = 1]. In fact, the CHA of quasisymmetric functions (QSym, η 0 ) is a terminal object in the category of CHA's, i.e. for each CHA (h, η) there is a unique combinatorial Hopf algebra morphism Ψ h : h → QSym.
Our goal here is to draw a parallel for Hopf monoids in vector species. We will see that the Hopf species WQSym will play the role of QSym in the Hopf monoids, and we will be able to build a unique Hopf monoid morphism from any combinatorial Hopf monoid h to WQSym, in line with what was done in [ABS06] and [Whi16].
In the last section we will investigate the consequence of this universal property on the Hopf structure of nestohedra and posets. We will use Theorem 3 and Proposition 39 to obtain that no combinatorial Hopf monoid map from Nesto to Pos exists.
Remark 40. The category of combinatorial Hopf monoids was introduced in two non equivalent ways, by [AA17] in vector species, which will be the one that we follow here, and by [Whi16] on pointed set species. We call comonoidal combinatorial Hopf monoid, or CCHM, to the latter, for sake of distinction. We also note that a stronger notion of character (or rather of stable objects) is employed for the comonoidal combinatorial Hopf monoid.
Indeed, in [Whi16], White shows that a comonoidal combinatorial Hopf monoid in colouring problems is a terminal object on the category of CCHM. Nevertheless, it is already advanced there, that if we consider the weaker notion of combinatorial Hopf monoid, the terminal object in such category, as here proposed, is indexed by set compositions. No counterpart of WQSym on pointed set species was found.

Hopf monoids in vector species
We recall the basic notions on Hopf monoids in vector species here, introduced in [AM10, Chapter 8]. We write Set × for the category of finite sets with bijections as only morphisms, and write V ec K for the category of vector spaces over K with linear maps as morphisms. A vector species is a functor a : Set × → V ec K , and this forms a category Sp K , where functors are natural transformations.
We can multiply species a, b to obtain a new vector species via the Cauchy product as follows: Two basic vector species are of interest. The first one I acts as the identity for · and is defined as I[∅] = K and as I[A] = 0 if A = ∅. The functor I sends morphisms to the identity. We also define the exponential vector species E as E[A] = K for any set A, and sends morphisms to the identity as well.
A vector species a is called a bimonoid if there are natural transformations µ : a · a ⇒ a, ι : I ⇒ a, ∆ : a ⇒ a · a and : a ⇒ I that satisfy some properties which we will recover here only informally. We address the reader to [AM10, Section 8.2 -8.3] for a detailed introduction of bimonoids in species.
• The natural transformation µ is associative.
• The natural transformation ι acts as unit on both sides.
• The natural transformation ∆ is coassociative.
• The natural transformation acts as a counit on both sides.
• The natural transformations satisfy some coherence relations typical in the Hopf algebra realm. In particular it satisfies diagram 26 below, which enforces that the multiplicative and comultiplicative structure agree.
We will denote vector species as a lowercase letter with a bar, and when we talk about Hopf monoids, we prioritize the use of the lower case 'h'. We will use µ A,B and · A,B for the monoidal product. Namely, · A,B will be employed for in line notation Proposition 41 (Proposition 8.10 in [AM10]). If h is a connected bimonoid, then there is an antipode on h that makes it a Hopf monoid.
• The exponential vector species can be endowed with a trivial product and coproduct. This is a connected bimonoid, hence it is a Hopf monoid. We will also consider here the Hopf species on graphs G, on posets Pos, on generalised permutahedra GP and on nestohedra Nesto.
• The vector space G[I] has a basis given by all graphs on the vertex set I.
• The vector space Pos[I] has a basis given by all posets on the vertex set I.
• The vector space GP[I] has a basis given by generalised permutahedra in R I . The products and coproducts are the natural ones that we already know from the Hopf algebra structure introduced above.
• The vector species Nesto, where Nesto[I] is spanned by all nestohedra on R I , is easily seen to be closed for product and coproduct introduced for GP, so it is a Hopf submonoid of GP.
Definition 43 (Morphisms in Hopf algebras). Given two Hopf algebras h 1 , h 2 and a natural transformation α : h 1 ⇒ h 2 , we say that it is a monoid morphism if the following commutes: We say that α is a comonoid morphism if the following commutes: Finally, we say that it is a Hopf algebra morphism if both diagrams (27) and (28) commute.

Combinatorial Hopf monoids
The notion of characters in Hopf monoids was already brought to light in [AA17], where it is used to settle, for instance, a conjecture of Humpert and Martin [HM12] on graphs.
Definition 44. Let h be a Hopf monoid. A Hopf monoid character η : h ⇒ E, or simply a character, is a monoid morphism.
In particular, the following diagram commutes: A combinatorial Hopf monoid is a pair (h, η) where h is a Hopf monoid, and η a character on h.
We write Ch(h) for the set of characters of a Hopf monoid h.
Example 45 (Combinatorial Hopf monoids). From the examples on Hopf monoids above, we will describe some combinatorial Hopf monoids by describing its action on the basis elements.
• The Hopf monoid on graphs G has the character η(G) = 1[G has no edges].
• The Hopf monoid on generalised permutahedra GP has the character given by η(q) = 1[q is a point ].
A combinatorial Hopf algebra morphism α : (h 1 , η 1 ) ⇒ (h 2 , η 2 ) is a Hopf algebra morphism α : h 1 ⇒ h 2 such that the following diagram commutes: We also introduce the Fock functors, that transform Hopf monoids in vector species into Hopf algebras, and more generally vector species into graded vector spaces. The topic is carefully developed in [AM10, Section 3.1, Section 15.1].
Definition 46 (Fock functors). Call gV ec K the category of graded vector spaces over K. We will focus on the following Fock functors K, K : Sp → gV ec K , called full Fock functor and bosonic Fock functor, respectively, defined as: where V Sn stands for the vector space of coinvariants on V over the action of S n , i.e. the quotient of V under all relations of the form x − σ(x), for σ ∈ S n .
If (h, η) is a combinatorial Hopf monoid in species with structure morphisms µ, ι, ∆, , then there is a Hopf algebra structure on K(h) and K(h).
• The Hopf algebra K(I) is the linear Hopf algebra K.
• The Hopf algebras K(G), K(Pos) and K(GP) are the Hopf algebras of graphs G, of posets Pos and of generalised permutahedra GP introduced earlier.
• The Hopf algebras K(Nesto) is the Hopf algebra Nesto, which is a Hopf subalgebra of GP.

The word quasisymmetric function combinatorial Hopf monoid
Recall that a colouring of a set I is a map f : I → N, and we let C I be the set of colourings of I. Recall as well that a set composition π = S 1 | · · · |S l can be identified with a total preorder R π , where we say a R π b if a ∈ S i and b ∈ S j satisfy i ≤ j. For a set composition π of A and a non-empty subset I ⊆ A, we define π| I as the set composition of I obtained by restricting the preorder R π to I. If I, J are disjoint sets, and f ∈ C I and g ∈ C J , then we set f * g ∈ C I J as the unique colouring in I J that satisfies both f * g| I = f and f * g| J = g.
For a set composition π ∈ C I , let M π = f ∈C I π(f )= π [f ] be a formal infinite sum of colourings, and define WQSym[I] as the span of {M π } π∈C I . This gives us a K-linear space with basis enumerated by C I .
We define the monoidal product operation with We write I < π J whenever there is no i ∈ I and j ∈ J such that j R π i. The coproduct ∆ I,J M π is M π| I ⊗ M π| J , whenever I < π J, and is zero otherwise. The unit ι ∅ (1) = M ∅ is the empty composition, and the counit acts on the basis as (M π ) = 1[ π = ∅]. This is called the dual Hopf monoid of faces Σ * = Σ * 1 in [AM10].
Definition 52 (Multi-character and other notations). For a set composition on I, π = S 1 | · · · |S l , denote for short and similarly define for a natural transformation ζ : h ⇒ b the linear transformation For a character, ζ[ π] : h[ π] → K ⊗l ∼ = K. For a set composition π on I of length l, let us define ∆ π as a map inductively as follows: • If the length of π is 1 or 0, then ∆ π = id h[I] .
• If π = S 1 | · · · |S l for l > 1, let τ = S 1 | · · · |S l−1 and define Note that this definition of ∆ π is independent of the chosen order in the inductive definition in (35), i.e. for any set I = A B and set composition π ∈ C I such that A < π B, we have by coassociativity of ∆. Then, we can define η π : h[I] → K as the composition Note that the close similarity of the notations η[ π] and η π will not lead to any ambiguity since both maps have different domains.
Finally, if A = I J and π ∈ C I , τ ∈ C J , then we write both π| τ and ( π, τ ) for the unique set composition γ ∈ C A such that γ| I = π, γ| J = τ , and I < γ J.
Note that diagram (26) corresponds to diagram (38) for γ = M |N . We see now that Diagram (38) is obtained by gluing diagrams of the form of Diagram (26): Proof. We will use induction on the length of γ, l := l( γ). The cases where l( γ) ≤ 1 are trivial, and if l( γ) = 2 we have already remarked that we recover diagram (26).
So, consider (38) for the set composition γ o = C 1 C 2 |C 3 | . . . |C l , which commutes by induction hypothesis, and apply the necessary twists so as to glue with with diagram (40). Then we obtain the commuting diagram: We note that absorbing the twist with the downward arrow and erasing the middle line gives us the desired diagram.
Taking the coefficients on the monomial basis for the first two items, this reduces to Proposition 55. The other two items are immediate. This concludes that Ψ h is a combinatorial Hopf monoid morphism.
We now justify uniqueness. Suppose that φ : h ⇒ WQSym is a combinatorial Hopf monoid morphism.
We now observe the relation between the Hopf algebras previously studied and the Fock functors of the Hopf monoids here described. First note that from (37) and from Lemma 14 we have that K(Ψ G ) = Ψ G is the chromatic symmetric function in non-commutative variables, and that K(Ψ G ) = Ψ G is the chromatic symmetric function.

Nestohedra and posets
A Hopf monoid morphism between Hopf monoids φ : h 1 ⇒ h 2 lifts to a mapping of characters φ * : Ch(h 2 ) → Ch(h 1 ) via φ * : η → η • φ. This lifting behaves well towards the terminal morphism Ψ h , as it can easily be seen: Hence, we have the following proposition: Lemma 56. If φ : h 1 ⇒ h 2 is a Hopf monoid morphism between two Hopf monoids with characters η 1 and η 2 respectively, such that the following diagram commutes: Then the following diagram commutes Corollary 57. There are no Hopf morphisms between the Hopf monoid of Pos and the Hopf monoid of Nesto, that commute with the given characters.
However, Ψ Pos is surjective, whereas we have seen in Proposition 39 that Ψ Nesto is not surjective. So there is no such map K(φ). This is a contradiction with the assumption that a combinatorial Hopf monoid morphism φ exists.