Combinatorial Hopf algebras from restriction species with preorder cuts

1. Problem Statement

The paper addresses the construction and unification of combinatorial Hopf algebras (CHAs). Traditional approaches to CHAs often rely on:

• Vector Spaces: Defining species in the category of vector spaces ($\mathbf{vect}$), which obscures the underlying combinatorial basis.
• Ad Hoc Definitions: Using set-theoretic comonoids that lack a rigorous categorical foundation (as comonoids do not naturally exist in the category of sets, $\mathbf{set}$, due to the lack of a null object).
• Limited Scope: Many known Hopf algebras (e.g., Malvenuto-Reutenauer, Loday-Ronco, Quasi-symmetric functions) are constructed via specific, isolated methods rather than a unified framework.

The author seeks a purely categorical framework that:

1. Retains the combinatorial nature of the objects (sets) while allowing for algebraic operations (like sums) via multimaps.
2. Provides a systematic method to generate bimonoid species (and thus Hopf algebras) by dualizing coproducts.
3. Explains how "avoidance" of specific patterns leads to quotient or sub-Hopf algebras.

2. Methodology

A. The Category $\mathbf{set}^{\mathbb{N}}$

The core innovation is replacing the category of sets ($\mathbf{set}$) or vector spaces ($\mathbf{vect}$) with $\mathbf{set}^{\mathbb{N}}$, the category of sets with multimaps.

• Objects: Sets.
• Morphisms: A multimap $f: X \to Y$ is a map $X \to \text{Hom}(Y, \mathbb{N})$, effectively assigning a multiset of $Y$ to each element of $X$. This can be represented by matrices with non-negative integer entries.
• Advantages:
  • It possesses a null object (the empty set), enabling the definition of comonoids.
  • It allows for dualization of morphisms (transposing the matrix), which is impossible in standard $\mathbf{set}$.
  • It bridges the gap between combinatorics (sets) and algebra (vector spaces), as the free vector space functor $F: \mathbf{set}^{\mathbb{N}} \to \mathbf{vect}$ preserves the structure.

B. Restriction Species over Preorders

The author introduces restriction species $S$ equipped with natural transformations to the species of preorders ($\mathbf{Pre}$).

• Restriction: For an injection $Y \hookrightarrow X$, there is a restriction map $S[X] \to S[Y]$.
• Preorder Cuts: A species $S$ is "over preorders" if there is a map $\pi: S \to \mathbf{Pre}$. For any $s \in S[X]$, $\pi(s)$ is a preorder on $X$.
• Coproduct Definition: The coproduct $\Delta: S[X] \to S[A] \times S[B]$ (where $X = A \sqcup B$) is defined based on whether $(A, B)$ is a cut for the preorder $\pi(s)$.
  • If $(A, B)$ is a cut (i.e., $A$ is a down-set and $B$ is an up-set), $\Delta(s) = (s|_A, s|_B)$.
  • Otherwise, $\Delta(s) = 0$.

C. Intertwined Coproducts and Bimonoids

The paper establishes a criterion for constructing bimonoids:

1. Start with a species $S$ having two structures as a restriction species over preorders, denoted $\pi_1$ and $\pi_2$.
2. These induce two coproducts, $\Delta_1$ and $\Delta_2$.
3. Intertwining Condition: The pair $(\Delta_1, \Delta_2)$ forms a bimonoid if the diagram relating the two coproducts (a "partial pullback diagram") commutes. Specifically, the diagram must satisfy the condition that for any decomposition $X = A \sqcup B \sqcup C \sqcup D$, the extension of local restrictions to a global element is unique and consistent with the cuts defined by $\pi_1$ and $\pi_2$.
4. Dualization: By dualizing one coproduct (say $\Delta_2$) to a product $\mu_2$, the pair $(\Delta_1, \mu_2)$ forms a bimonoid species. Applying the Fock functor converts this into a Hopf algebra.

D. Avoidance and Quotients

The paper investigates avoidance:

• Let $A$ be a subspecies of "forbidden" configurations.
• $S \setminus A$ is the subspecies of elements avoiding $A$.
• If a coproduct is $A$-irreducible (meaning if an element has a forbidden part, its coproduct components must also have a forbidden part), then $S \setminus A$ forms a quotient bimonoid species. This allows the systematic generation of quotient Hopf algebras.

3. Key Contributions and Results

A. New Hopf Algebras of Permutations

The author constructs a vast family of quotient Hopf algebras of the Malvenuto-Reutenauer (MR) algebra:

• Mechanism: The MR algebra is viewed as a restriction species over preorders where $\pi_1$ and $\pi_2$ relate to the global descent structure of permutations.
• Result (Theorem 8.2): For any set of permutations $A$ that have no global descents, the subspecies of permutations avoiding $A$ forms a quotient Hopf algebra of the MR algebra.
• Examples:
  • Avoiding $\{213\}$ yields the Loday-Ronco Hopf algebra (planar binary trees).
  • Avoiding $\{213, 132\}$ yields the Quasi-symmetric functions algebra.
  • Avoiding $\{3142, 2413\}$ yields the WPP algebra (plane posets).

B. Parking Filtrations

A new "master" Hopf algebra is introduced based on pairs of parking filtrations.

• Structure: Elements are pairs of filtrations $\{X_i\}, \{Y_j\}$ on a set $X$.
• Result: This algebra contains the standard Parking Function Hopf algebra (Novelli-Thibon) as a sub-algebra and the MR algebra as a further quotient. This unifies these structures under a single framework of pairs of preorders.

C. Four Master Hopf Algebras of Preorder Pairs

The paper classifies pairs of preorders $(P, Q)$ into four types based on how their cuts interact:

1. cc (comparable-comparable): $A <_1 D$ and $A <_2 D$.
2. nc (non-comparable-comparable): $A \parallel_1 D$ and $A <_2 D$.
3. cn (comparable-non-comparable): Symmetric to nc.
4. nn (non-comparable-non-comparable): $A \parallel_1 D$ and $A \parallel_2 D$.

• Result: Each type forms a distinct "master" Hopf algebra.
  • The cc type generalizes the MR algebra.
  • The nc type relates to the algebra of packed words ($WQSymm$).
  • The nn type relates to matrices of natural numbers (up to row/column permutations).

4. Significance

1. Unification: The paper provides a single categorical framework ($\mathbf{set}^{\mathbb{N}}$ + restriction species over preorders) that generates and relates many disparate Hopf algebras (MR, Loday-Ronco, Quasi-symmetric, Parking, Graph, Poset algebras).
2. Categorical Rigor: It resolves the issue of defining comonoids in set-based combinatorics by introducing multimaps, allowing for a purely categorical derivation of Hopf structures without ad hoc definitions.
3. Systematic Construction of Quotients: The concept of $A$-irreducibility provides a general recipe for identifying when pattern avoidance leads to a valid quotient Hopf algebra, explaining why certain pattern-avoiding sets (like those without global descents) work while others do not.
4. New Structures: It introduces novel objects like the "master" Hopf algebra of pairs of parking filtrations and the four classes of preorder pairs, expanding the landscape of known combinatorial Hopf algebras.

In summary, Fløystad's work shifts the perspective from defining Hopf algebras via specific combinatorial rules to deriving them from the structural properties of restriction species and preorder cuts, offering a powerful, generalizable tool for combinatorial algebra.