Multi-tree insertion on nonplanar trees #
This file defines UnorderedTree.insertion T G, the multiset, over all assignments of the guests
G to vertices of T, of the trees obtained by grafting each guest at its vertex, and
UnorderedTree.insertionMultiset F G, the same for a host forest F. This is Foissy's formula
for the Guin–Oudom extension of the grafting product. Both are defined by recursion on the host:
grafting into node a A places some guests under the root and grafts the rest into the forest
A, and grafting into a forest splits the guests among its trees. From it the file defines
UnorderedTree.productMultiset F G, the forests of the Grossman–Larson product F ⋆ G: over the
splits G = G₁ + G₂, the graftings of G₂ into F with G₁ placed alongside.
Main results #
insertion_mk,insertionMultiset_mk: the recursion computesRoseTree.insertionandRoseTree.insertionForeston planar representatives.insertionMultiset_singleton_node: grafting into a single nodenode a Aputs the forests ofA ⋆ Bunder the root.insertionMultiset_add_host: grafting into a disjoint union splits the guests between the two parts, the ruleAB ∘ C = (A ∘ C₍₁₎)(B ∘ C₍₂₎)of Oudom and Guin's Proposition 3.7.insertionMultiset_antidiagonal: splits of an output forest are splits of the host and of the guests, each guest following its host.productMultiset_zero_left,productMultiset_zero_right: the empty forest is a unit.productMultiset_bind_antidiagonal: splits of the forests ofF ⋆ Gare products of splits ofFand ofG.
Implementation notes #
Grafting into a forest is a Multiset.foldr of insertionStep over its trees. The fold is well
defined because splitting the guests three ways is symmetric in the first two parts, so no
invariance under reordering of children is needed.
References #
One step of grafting into a forest. The guests split between a first tree, whose graftings
are k, and the remaining trees, whose graftings are acc.
Equations
- One or more equations did not get rendered due to their size.
Instances For
insertion T G is the multiset, over the assignments of the trees of G to vertices of T,
of the trees obtained by grafting each guest at its vertex.
Equations
- One or more equations did not get rendered due to their size.
Instances For
insertionMultiset F G is the multiset, over the assignments of the trees of G to vertices
of F, of the forests obtained by grafting each tree at its vertex.
Equations
- One or more equations did not get rendered due to their size.
Instances For
insertionMultiset computes RoseTree.insertionForest on planar representatives.
Grafting into A gives a single tree with root a only if A is one.
Splits of an output forest are splits of the host and of the guests, each guest following its host.
Grafting into a disjoint union splits the guests between the two parts.
The Grossman–Larson product #
productMultiset F G is the multiset of forests in the Grossman–Larson product F ⋆ G: over
the splits G = G₁ + G₂, the forests X + G₁ with X a grafting of the trees of G₂ onto F.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Grafting into a single node node a A puts the forests of A ⋆ B under the root: each guest
is a new child of the root or grafted into A.
Splits of a product #
Splitting the forests of F ⋆ G is splitting F and G and multiplying the parts. This is the
multiset form of the compatibility between the Grossman–Larson product and the coproduct of the
symmetric algebra, Oudom and Guin's Lemma 3.11.
Splitting the forests of A ⋆ B is splitting A and B and multiplying the parts.