Hopf algebra of labeled simple graphs arising from super-shuffle product

1.   Introduction

In 1964, Hopf first proposed Hopf algebra in order to study the properties of algebraic topology and algebraic groups ^[1]. In 1965, Milnor and Moore introduced the basic definitions and properties of Hopf algebras ^[2], then Chase and Sweedler did some relevant works and introduced common notations ^[3,4]. After that, Hopf algebra has been used to study a lot of objects, such as posets ^[5], symmetric functions ^[6,7], quantum groups ^[8], and Clifford algebras ^[9].

In 1979, Joni and Rota first studied Hopf algebras on combinatorial objects, such as polynomials and puzzles ^[10]. In 1994 and 1995, Schmitt studied incidence Hopf algebras and a Hopf algebra on graphs with an addition invariant and introduced a variety of examples of incidence Hopf algebras arising from families of graphs, matroids, and distributive lattices, many of which generalize well-known Hopf algebras ^[11,12].

In 1997 and 1999, Connes and Kreimer studied Hopf algebra structures on rooted trees and rooted forests and their applications in renormalization in quantum field theories ^[13,14]. This promotes the study of Hopf algebras on graphs. In 2020, Aval et al. mentioned a Hopf algebra on labeled graphs arising from the unshuffle coproduct ^[15]. For more Hopf algebras on graphs, please refer to ^{[16,17,18,19,20]}.

Permutations are related to graphs closely. In 1995, Malvenuto and Reutenauer studied a Hopf algebra on permutations, where the product is the classic shuffle Ⅲ ^[21]. In 2014, Vargas defined a commutative but non-cocommutative Hopf algebra on permutations by the super-shuffle product Ⅲ and the cut-box coproduct $\Delta_{\diamond}$ without a proof ^[22], which was done by Liu and Li in 2021 ^[23]. In 2020, Zhao and Li defined another commutative Hopf algebra structure on permutations and its duality and figured out closed-formulas of the antipodes ^[24]. It is well-known that permutations are elements of symmetric groups, which are widely used in various fields, such as the algebraic number theory ^[25].

A labeled simple graph is a simple graph with vertices labeled by distinct positive integers. In this paper, we generalize the super-shuffle product and the cut-box coproduct on permutations to labeled simple graphs. We prove that the vector space spanned by labeled simple graphs with these two operations is a Hopf algebra.

This paper is organized as follows. In Section 2, we review some basic concepts of Hopf algebra, give the definition of labeled simple graphs, and define the super-shuffle product and the cut-box coproduct on labeled simple graphs. In Section 3, we prove that the vector space spanned by labeled simple graphs is a graded algebra with the super-shuffle product and a graded coalgebra with the cut-box coproduct. Furthermore, we prove the compatibility of these operations, then the vector space is a Hopf algebra. Finally, we summarize our main conclusions in Section 4.

2.   Basic definitions

2.1.   Preliminaries

Here, we recall some basic definitions related to Hopf algebra and see ^[4] for more details. Let $C$ be a $\mathbb{K}$-module over commutative ring $\mathbb{K}$.

Define $\mathbb{K}$-bilinear mappings $m$ from $C\otimes C$ to $C$ and $\mu$ from $\mathbb{K}$ to $C$, such that the diagrams in Figure 1 are commutative, then $(C, m, \mu)$ is a $\mathbb{K}$-algebra. Here, $m$ and $\mu$ are called a product and a unit, respectively.

Define $\mathbb{K}$-linear mappings $\Delta$ from $C$ to $C\otimes C$ and $\nu$ from $C$ to $\mathbb{K}$, such that the diagrams in Figure 2 are commutative, then $(C, \Delta, \nu)$ is a $\mathbb{K}$-coalgebra. Here, $\Delta$ and $\nu$ are called a coproduct and a co-unit, respectively.

We say $(C, m, \mu, \Delta, \nu)$ is a bialgebra if $(C, m, \mu)$ is an algebra, $(C, \Delta, \nu)$ is a coalgebra, and one of the following compatibility conditions holds:

(ⅰ) $\Delta$ and co-unit $\nu$ are algebra homomorphisms;

(ⅱ) $m$ and unit $\mu$ are coalgebra homomorphisms.

In fact, (ⅰ) and (ⅱ) are equivalent; see ^[26] for details.

A vector space $C$ is graded if

and we call it connected when $C_0\cong\mathbb{K}$ ^[26]. The algebra $(C, m, \mu)$ is graded if the product $m$ satisfies

and

Similarly, the coalgebra $(C, \Delta, \nu)$ is graded if the coproduct $\Delta$ satisfies

and

when $n\geqslant 1$. A bialgebra is graded when its algebra and coalgebra structures are both graded.

For bialgebra $(C, m, \mu, \Delta, \nu)$, we call $S$: $C\rightarrow C$ an antipode if it satisfies

i.e., the diagram in Figure 3 is commutative. A bialgebra is a Hopf algebra when it has an antipode.

Actually, a graded connected bialgebra must be a Hopf algebra ^[26].

2.2.   Main concepts

In this subsection, we recall some basic concepts of graph theory, which can be found in ^[27].

A labeled simple graph $\Gamma = (V, E)$ is a finite graph with no cycles and no multiple edges whose vertices are distinct positive integers, where $V$ is the set of all vertices of $\Gamma$, also denoted by $V(\Gamma)$, and $E$ is the set of all edges of $\Gamma$, also denoted by $E(\Gamma)$. Obviously, $E\subseteq V\times V$. If $(i_1, i_2)\in E$, then $i_1\neq i_2$ and $(i_2, i_1)\notin E$, since the graph $\Gamma$ has no cycles and no multiple edges. In particular, $\Gamma$ is the empty graph when $V = \emptyset$, denoted by $\epsilon$.

Let $\Gamma = (V, E)$ and $I\subseteq V$. Define the restriction of $\Gamma$ on $I$ by $\Gamma_I = (I, E_I)$, where

and we call $\Gamma_I$ a subgraph of $\Gamma$. If $I$ is a nontrivial subset of $V$, we call $\Gamma_I$ a true subgraph of $\Gamma$. If the vertex sets of two subgraphs of $\Gamma$ are disjoint, then we say that the subgraphs are disjoint subgraphs. If

and

then denote

Obviously, there are no edges between $V_1$ and $V_2$.

We introduce the following notations for convenience:

and

Example 1. The labeled simple graph

can be represented as the graph

then

Let

and $\mathcal{H}_n$ be the vector space spanned by $H_n$ over field $\mathbb{K}$, for a nonnegative integer $n$. In particular, $H_0 = \{\epsilon\}$ and $\mathcal{H}_0 = \mathbb{K}H_0$. Denote

Let $\Gamma = (V, E)$ be a nonempty labeled simple graph, where

Define the restructure of $\Gamma = (V, E)$ by $\hat{V}$ to be $\hat{\Gamma} = (\hat{V}, \hat{E})$, where

is a set of distinct positve integers satisfying

and $\hat{E}$ satisfies

for any $1\leqslant i, j \leqslant n$.

Example 2. For

the restructure of $\Gamma$ by $[5]$ is and the restructure of $\Gamma$ by $\{1, 3, 5, 7, 9\}$ is

Let $I$ be the set $\{i_1, i_2, \cdots, i_n\}$ of distinct positive intergers with $i_1 < i_2 < \cdots < i_n$. We define a mapping $\text{st}_I$ from $I$ to $[|I|]$ to be the standardization of $I$ satisfying $\text{st}_I(i_a) = a$ for $1\leqslant a\leqslant n$. For $x, y\in I$, we have $\text{st}_I(x) < \text{st}_I(y)$ if, and only if, $x < y$. For a subset $S$ of $I$, denote

In general, the standardizations of a number in different sets are different. For example, let $I_1 = \{6, 7, 9\}$ and $I_2 = \{1, 3, 7, 9, 11\}$, then $\text{st}_{I_1}(7) = 2$ and $\text{st}_{I_2}(7) = 3.$ For convenience, we omit the subscript of the set.

Define the standard form of $\Gamma = (V, E)$ by $\text{st}(\Gamma) = (\text{st}(V), \text{st}(E))$, where $\text{st}(V) = [|V|]$ and $\text{st}(E)$ satisfies

Obviously, the above standardizations are of the vertex set $V$, so we omit the subscript. In particular, we have $\text{st}(\epsilon) = \epsilon$. Thus, $\text{st}(\cdot)$ is a mapping from the set of all labeled simple graphs to $H$. In fact, the standard form of $\Gamma = (V, E)$ is the restructure of $\Gamma$ by $[|V|]$.

In addition, for a positive integer $n$, let $\Gamma^{\uparrow n}$ be the restructure of $\Gamma$ by the set

Similarly, let $\Gamma^{\downarrow n}$ be the restructure of $\Gamma$ by the set

provided $n$ is less than the minimum of $V$.

Example 3. For labeled simple graphs

their standard forms are

and

For nonempty $\Gamma$ in $H$, the standard form of any restructure of $\Gamma$ must be $\Gamma$, i.e.,

where the $\hat{\Gamma}$ is a restructure of $\Gamma$. Conversely, if the standard form of a labeled simple graph is $\Gamma$, then it must be a restructure of $\Gamma$.

Example 4. For

the restructure of $\Gamma$ by $[4, 8]$ is and the restructure of $\Gamma$ by $\{1, 3, 5, 7, 9\}$ is . We have

For $\Gamma = ([n], E)$ in $H_n$, we call $i$ a split of $\Gamma$ if

where $0\leqslant i\leqslant n$. Obviously, $i$ is a split of $\Gamma$ if, and only if, there are no edges between $[i]$ and $[i+1, n]$ in $\Gamma$. By the definition, $0$ and $n$, called trivial splits, are always splits of labeled simple graphs in $H_n$ when $n\geqslant 1$. We call $\Gamma$ indecomposible if it is nonempty and only has trivial splits.

For $\Gamma = ([n], E)$ in $H_n$, $n\geqslant 1$, assume that $\{i_0, i_1, \cdots, i_{s}\}$ is the set of all splits of $\Gamma$, where

then we call $\Gamma_{[i_{k-1}+1, i_k]}$ an atom of $\Gamma$, $1\leqslant k\leqslant s$. Obviously, the standard form of an atom is indecomposible since there is no split of $\Gamma$ in $[i_{k-1}+1, i_k]$ for $1\leqslant k\leqslant s$. Let

for $1\leqslant k\leqslant s$. We define the decomposition of $\Gamma$ by

Actually, if $j_k$: $= i_{k}-i_{k-1}$, then $\Gamma_k\in H_{j_k}$ for $1\leqslant k\leqslant s$, and

In particular, when $\Gamma = \epsilon$, its decomposition is itself.

Example 5. (1) The set of splits of is $\{0, 2, 5\}$ and its decomposition is

The atoms of

(2) The set of splits of is $\{0, 2, 4, 5\}$, so its decomposition is

The atoms of

(3) The set of splits of is $\{0, 3\}$, so it is indecomposible. Its decomposition is itself, and so is its atom.

Define the cut-box coproduct ${\Delta}$ on $\mathcal{H}$ by

for nonempty

in $H_n$ with splits

Define the co-unit $\nu$ from $\mathcal{H}$ to $\mathbb{K}$ by

for $\Gamma$ in $H$.

Example 6.

Theorem 2.1. $(\mathcal{H}, {\Delta}, \nu)$ is a graded coalgebra.

Proof. It is easy to verify that $\nu$ is a co-unit. Obviously,

Suppose $\Gamma = ([n], E)$ with $n\geqslant 1$, and its decomposition is

then,

where

for $0\leqslant k\leqslant s$. So, ${\Delta}$ satisfies the coassociative law. Hence, $(\mathcal{H}, {\Delta}, \nu)$ is a coalgebra.

By the definition of the coproduct ${\Delta}$, we have

and

when $n\geqslant 1$. So, $(\mathcal{H}, {\Delta}, \nu)$ is a graded coalgebra. □

Define the super-shuffle product $*$ on $\mathcal{H}$ by

for $\Gamma_1$ in $H_m$ and $\Gamma_2$ in $H_n$. Sometimes, we denote it by $*(\Gamma_1, \Gamma_2)$. Obviously, the product $*$ is commutative on $\mathcal{H}$. Define the unit $\mu$ from $\mathbb{K}$ to $\mathcal{H}$ by $\mu(1) = \epsilon$.

Actually, $\Gamma_I$ is the restructure of $\Gamma_1$ by $I$, and $\Gamma_J$ is the restructure of $\Gamma_2$ by $J$ in (2.1). Given $I$ and $J$ satisfying $|I| = m$, $|J| = n$, and $I\cup J = [m+n]$, $\Gamma$ traverses all graphs in $H_{m+n}$, which is a union of the restructure of $\Gamma_1 = (V_1, E_1)$ by $I$, the restructure of $\Gamma_2 = (V_2, E_2)$ by $J$, and some edges between $\hat{V}_1$ and $\hat{V}_2$. That is, $\Gamma$ traverses the set

So, we rewrite (1) as

That is, each term $\Gamma$ in $\Gamma_1*\Gamma_2$ is a graph by adding some edges between $\hat{V}_1$ and $\hat{V}_2$ to $\hat{\Gamma}_1\cup\hat{\Gamma}_2$, where

i.e.,

where $C$ is a set of edges between $\hat{V}_1$ and $\hat{V}_2$. Conversely, $(\hat{V}_1, \hat{V}_2, C)$ can uniquely determine a term in $\Gamma_1*\Gamma_2$, where

and $C$ is a set of edges between $\hat{V}_1$ and $\hat{V}_2$. We consider two terms in $\Gamma_1*\Gamma_2$ the same if, and only if, their corresponding $\hat{V}_1$, $\hat{V}_2$ and $C$ are the same. Thus, each term in $\Gamma_1*\Gamma_2$ is unique.

Example 7.

Here, we color the vertices of the term $\Gamma$ in $\Gamma_1*\Gamma_2$ restricted to $\Gamma_1$ red and to $\Gamma_2$ blue, respectively. In this example, although and are the same as graphs, we consider that they are different in $\Gamma_1*\Gamma_2$ because their $\hat{V}_1$ and $\hat{V}_2$ are not the same. So, each term in $\Gamma_1*\Gamma_2$ is unique.

In order to represent vertices in each term of $\Gamma_1*\Gamma_2$ before restructure, we name the vertices in $\Gamma_1$ and $\Gamma_2$, respectively, as

and

where $v_{11} < v_{12} < \cdots < v_{1m}$ and $v_{21} < v_{22} < \cdots < v_{2n}$. Although $v_{11}$ and $v_{21}$ are both equal to $1$, we consider that they are different because they belong to different graphs, then the vertex set of a term in $\Gamma_1*\Gamma_2$ is

Theorem 2.2. $(\mathcal{H}, *, \mu)$ is a graded algebra.

Proof. It is easy to verify that $\mu$ is a unit. Suppose

and

in $H$. For any term $\Gamma$ in $(\Gamma_1*\Gamma_2)*\Gamma_3$, it corresponds to two disjoint subsets $J\text{ and }K$ of $[n_1+n_2+n_3]$ with $|J| = n_1+n_2$ and $|K| = n_3$, such that $\text{st}(\Gamma_J)$ is a term in $\Gamma_1*\Gamma_2$ and $\text{st}(\Gamma_K) = \Gamma_3$. It means

For a fixed $J$ in (4), $\text{st}(\Gamma_{J})$ corresponds to two disjoint subsets $P\text{ and }Q$ of $[n_1+n_2]$ with $|P| = n_1$ and $|Q| = n_2$, such that

and

Therefore, there is a subset $M$ of $J$ with $|M| = n_1$ corresponding to $P$, i.e., $\text{st}_J(M) = P$, such that

Similarly, there is a subset $N$ of $J$ with $|N| = n_2$ corresponding to $Q$, i.e., $\text{st}_J(N) = Q$, such that

That means (4) can be rewritten as

For a fixed subset $J$ in $[n_1+n_2+n_3]$ with cardinality $n_1+n_2$, $P$ traverses all subsets with cardinality $n_1$ in $[n_1+n_2]$ since $\text{st}(\Gamma_J)$ traverses all terms in $\Gamma_1*\Gamma_2$. Meanwhile, $M$ traverses all subsets with cardinality $n_1$ in $J$. Therefore, $M$ traverses all subsets with cardinality $n_1$ in $[n_1+n_2+n_3]$ since $J$ traverses all subsets with cardinality $n_1+n_2$ in $[n_1+n_2+n_3]$. At the same time, $N$ traverses all subsets with cardinality $n_2$ in $[n_1+n_2+n_3]$ from $J = M\cup N$. Thus, (5) can be rewritten as

Similarly, $\Gamma_1*(\Gamma_2*\Gamma_3)$ is equal to (6). Hence, $*$ satisfies the associative law and $(\mathcal{H}, *, \mu)$ is an algebra.

By the definition of the product $*$, we have

and

So, $(\mathcal{H}, *, \mu)$ is a graded algebra. □

3.   Main theorems

In this section, we will prove that $(\mathcal{H}, *, \mu, {\Delta}, \nu)$ is a Hopf algebra. Now, we give two lemmas.

Let $\Gamma_1 = (V_1, E_1)$ in $H_m$ and $\Gamma_2 = (V_2, E_2)$ in $H_n$ be nonempty graphs and $\Gamma$ be a term in $\Gamma_1*\Gamma_2$. Thus, $\Gamma$ can be represented by $(\hat{V}_1\cup\hat{V}_2, \hat{E}_1\cup\hat{E}_2\cup C)$ from (3), where

is the restructure of $\Gamma_1$ by $\hat{V}_1$ and

is the restructure of $\Gamma_2$ by $\hat{V}_2$. Obviously,

Lemma 3.1. Each atom of $\Gamma$ in $\Gamma_1*\Gamma_2$ can only contain subgraphs of $\hat{\Gamma}_1$ or $\hat{\Gamma}_2$ corresponding to some complete atoms in $\Gamma_1$ or $\Gamma_2$.

Proof. Let

and

be nonempty in $H$, where $v_{11} < \cdots < v_{1m}$ and $v_{21} < \cdots < v_{2n}$. Consider a term $\Gamma$ in $\Gamma_1*\Gamma_2$. Suppose $\Gamma_{[i, j]}$ is an atom of $\Gamma$ containing a nonempty subgraph of ${\hat{\Gamma}_1}$$_{\{\hat{v}_{1k}\}_{k = p}^q}$, where ${\hat{\Gamma}_1}$$_{\{\hat{v}_{1k}\}_{k = p}^q}$ corresponds to the atom ${\Gamma_1}_{\{v_{1k}\}_{k = p}^q}$ of $\Gamma_1$.

When $p = q$, there is only one element in $\{\hat{v}_{1k}\}_{k = p}^q$, then $\Gamma_{[i, j]}$ contains the complete atom ${\hat{\Gamma}_1}$$_{\{\hat{v}_{1k}\}_{k = p}^q}$. Hence, the conclusion holds.

When $1\leqslant p < q\leqslant m$, ${\{v_{1k}\}_{k = p}^{q}}$ contains at least two vertices. Suppose that $\Gamma_{[i, j]}$ contains a true subgraph of ${\hat{\Gamma}_1}$$_{\{\hat{v}_{1k}\}_{k = p}^q}$. In fact, since $\{\hat{v}_{1k}\}_{k = p}^q$ maintains the order relationship in $\{v_{1k}\}_{k = p}^q$, the vertices of this true subgraph correspond to a true subinterval in $\{v_{1k}\}_{k = p}^q$. Let

and

We have $i\leqslant \hat{v}_{1\omega}\leqslant \hat{v}_{1\Omega}\leqslant j$, then

and $\omega\neq p$ or $\Omega\neq q$ because $\Gamma_{[i, j]}$ contains a true subgraph of ${\hat{\Gamma}_1}$$_{\{v_{1k}\}_{k = p}^q}$.

If $\omega\neq p$, then $\omega > p$. From

and

From $\Gamma_{[i, j]}$ is an atom of $\Gamma$ and $i-1$ is a split of $\Gamma$, there are no edges between $[i-1]$ and $[i, m+n]$ in $\Gamma$. Therefore,

By the definition of $*$, we have

and

Hence,

where $p-1 < \omega-1 < q$, i.e., $\omega-1$ is a split of $\Gamma_1$. However, there is no split of $\Gamma_1$ between $p-1$ and $q$, since ${\Gamma_1}_{\{v_{1k}\}_{k = p}^{q}}$ is an atom of $\Gamma_1$, which is a contradiction. Similarly, when $\Omega\neq q$, we have $p-1 < \Omega < q$ and $\Omega$ is a split of $\Gamma_1$, a contradiction.

Thus, if an atom of $\Gamma$ contains a true subgraph in $\hat{\Gamma}_1$, then this subgraph must correspond to some complete atoms of $\Gamma_1$. Similarly, we can prove the conclusion holds for atoms in $\Gamma_2$. □

For simplicity, we restate Lemma 3.1 as: for any term $\Gamma$ in $\Gamma_1*\Gamma_2$, any atom of $\Gamma$ can only contain some complete original atoms of $\Gamma_1$ or $\Gamma_2$.

Remark 3.1. For $\Gamma$ in $H_n$, suppose its decomposition is

with splits

then

If $\Theta_1\otimes\Theta_2$ is the term in $\Delta(\Gamma)$, then $\Theta_1$ is a standard form of the first $k$ atoms of $\Gamma$ for some $0\leqslant k\leqslant s$. Let $\Gamma$ be a term in $\Gamma_1*\Gamma_2$ and $\Theta_1\otimes \Theta_2$ be a term in ${\Delta}(\Gamma)$. From Lemma 3.1, $\Theta_1$ only contains the standard forms of some complete original atoms of $\Gamma_1$ or $\Gamma_2$. If the first few atoms of a labeled simple graph contain $l$ vertices, then these vertices must be $[l]$. So, if $\Theta_1$ contains $i$ original atoms of $\Gamma_1$, then they must be the first $i$ atoms of $\Gamma_1$. Similarly, if $\Theta_1$ contains $j$ original atoms of $\Gamma_2$, then they must be the first $j$ atoms of $\Gamma_2$.

Let $\Gamma_1$ and $\Gamma_2$ be nonempty in $H$. Suppose their decompositions are

and

Define ${\Delta}_{ij}(\Gamma_1*\Gamma_2)$ to be the sum of all terms $\Theta_1\otimes \Theta_2$ in ${\Delta}(\Gamma_1*\Gamma_2)$, where $\Theta_1$ contains the first $i$ complete original atoms in $\Gamma_1$ and the first $j$ complete original atoms in $\Gamma_2$, $0\leqslant i\leqslant s$, and $0\leqslant j\leqslant t$.

Lemma 3.2. Let $\Gamma_1$ and $\Gamma_2$ be nonempty in $H$. Assume their decompositions are

then,

for $0\leqslant i\leqslant s$ and $0\leqslant j\leqslant t$.

Proof. Denote

and

Similarly,

and

Obviously,

and

Next, we denote $\hat{V}_{11}$ as the subset corresponding to $V_{11}$ in $\hat{V}_1$ and $(\hat{V}_{11}, \hat{E}_{11})$ as the restructure $(V_{11}, E_{11})$ by $\hat{V}_{11}$. Similarly, we have $\hat{V}_{12}$, $\hat{E}_{12}$, $\hat{V}_{21}$, $\hat{E}_{21}$, $\hat{V}_{22}$, and $\hat{E}_{22}$.

By (3), each term $\Gamma$ in $\Gamma_1*\Gamma_2$,

where $C$ is a set of edges between $\hat{V}_1$ and $\hat{V}_2$. Let $\Theta_1\otimes\Theta_2$ be a term in ${\Delta}(\Gamma)$ and in ${\Delta}_{ij}(\Gamma_1*\Gamma_2)$. By the definition of ${\Delta}_{ij}$, $h_1+h_2$ is a split of $\Gamma$,

and

Since $h_1+h_2$ is a split of $\Gamma$, there are no edges between $[h_1+h_2]$ and $[h_1+h_2+1, m+n]$ in $\Gamma$. Thus, there are no edges between $\hat{V}_{11}$ and $\hat{V}_{22}$ and no edges between $\hat{V}_{12}$ and $\hat{V}_{21}$. Therefore, $C$ is $C_1\cup C_2$, where

and

Hence,

Therefore,

and

then $\Theta_1$ is a term in

for

and

Similarly, $\Theta_2$ is a term in

For given $\Theta_1$ in $\Gamma_{11}\diamond \cdots\diamond \Gamma_{1i}*\Gamma_{21}\diamond \cdots\diamond \Gamma_{2j}$, let

For each $\Gamma$ in $S$,

by (7), where $\hat{V}_{11}, \hat{V}_{21}$, and $C_1$ are fixed, since $\Theta_1$ is fixed.

By (3), when $\Gamma$ traverses all terms in $\Gamma_1*\Gamma_2$, its $\hat{V}_1$ and $\hat{V}_2$ traverse all disjoint subsets of $[m+n]$ with cardinalities $m$ and $n$, respectively, and $C$ traverses all subsets in $\hat{V}_1\times\hat{V}_2$ for fixed $\hat{V}_1$ and $\hat{V}_2$. Thus, $\hat{V}_{12}$ and $\hat{V}_{22}$ of $\Gamma$ in $S$ traverse all disjoint subsets of $[h_1+h_2+1, m+n]$ with cardinalities $m-h_1$ and $n-h_2$, respectively. Also, $C_2$ of $\Gamma$ in $S$ traverses all subsets of $\hat{V}_{12}\times \hat{V}_{22}$ for fixed $\hat{V}_{12}$ and $\hat{V}_{22}$. Correspondingly, for $\hat{V}_{12}$ and $\hat{V}_{22}$ of $\Gamma$ in $S$, $\text{st}_{\hat{V}_{12}\cup\hat{V}_{22}}(\hat{V}_{12})$ and $\text{st}_{\hat{V}_{12}\cup\hat{V}_{21}}(\hat{V}_{22})$ traverse all disjoint subsets of $[m+n-h_1-h_2]$ with cardinalities $m-h_1$ and $n-h_2$, respectively. Also, $\text{st}_{\hat{V}_{12}\cup\hat{V}_{22}}(C_2)$ traverses all subsets in

for fixed $\hat{V}_{12}$ and $\hat{V}_{22}$. From the arguments above and (2), for fixed $\Theta_1$ in $\Gamma_{11}\diamond \cdots\diamond \Gamma_{1i}*\Gamma_{21}\diamond \cdots\diamond \Gamma_{2j}$, $\Theta_2$ traverses all terms in $\Gamma_{1, i+1}\diamond \cdots\diamond\Gamma_{1s}*\Gamma_{2, j+1}\diamond \cdots\diamond\Gamma_{2t}$. Similarly, for fixed $\Theta_2$ in $\Gamma_{1, i+1}\diamond\cdots\diamond\Gamma_{1s}*\Gamma_{2, j+1}\diamond\cdots\diamond\Gamma_{2t}$, $\Theta_1$ traverses all terms in $\Gamma_{11}\diamond\cdots\diamond\Gamma_{1i}*\Gamma_{21}\diamond\cdots\diamond \Gamma_{2j}$. Therefore,

□

Next, we show that $(\mathcal{H}, *, \mu, {\Delta}, \nu)$ is a Hopf algebra.

Theorem 3.1. $(\mathcal{H}, *, \mu, {\Delta}, \nu)$ is a bialgebra.

Proof. It is easy to verify $\nu$ is an algebra homomorphism. We only need to prove ${\Delta}$ is an algebra homomorphism, i.e.,

for $\Gamma_1$ and $\Gamma_2$ in $H$.

If $\Gamma_1$ or $\Gamma_2$ is an empty graph, then (8) holds. Suppose

in $H_m$ and

in $H_n$ are nonempty graphs. Let

By Lemma 3.2, we have

Furthermore,

Hence, $(\mathcal{H}, *, \mu, {\Delta}, \nu)$ is a bialgebra. □

Example 8.

Corollary 3.1. $(\mathcal{H}, *, \mu, {\Delta}, \nu)$ is a Hopf algebra.

Proof. Since $(\mathcal{H}, *, \mu, \Delta, \nu)$ is a graded connected bialgebra, it is a Hopf algebra. □

4.   Conclusions

Many combinatorial objects have Hopf algebra structures. The labeled simple graphs are important combinatorial objects. In this paper, we generalize the super-shuffle product and the cut-box coproduct on permutations to labeled simple graphs. We prove that the vector space spanned by labeled simple graphs with the super-shuffle product and the cut-box coproduct is a Hopf algebra. In the future, we will study the duality of the Hopf algebra $(H, *, \mu, \Delta, \nu)$.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

This work is supported by National Natural Science Foundation of China (Nos. 11701339 and 12071265).

Conflict of interest

The authors declare that there are no conflicts of interest in this paper.