Documentation

Linglib.Core.Algebra.RootedTree.PreLie.InsertionUnordered

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 #

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 #

def UnorderedTree.insertionStep {α : Type u_1} (k : Multiset (UnorderedTree α) → Multiset (UnorderedTree α)) (acc : Multiset (UnorderedTree α) → Multiset (Multiset (UnorderedTree α))) (G : Multiset (UnorderedTree α)) :
Multiset (Multiset (UnorderedTree α))

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
    def UnorderedTree.insertion {α : Type u_1} :
    UnorderedTree α → Multiset (UnorderedTree α) → Multiset (UnorderedTree α)

    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
      def UnorderedTree.insertionMultiset {α : Type u_1} (F G : Multiset (UnorderedTree α)) :
      Multiset (Multiset (UnorderedTree α))

      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
        theorem UnorderedTree.insertion_node {α : Type u_1} (a : α) (A G : Multiset (UnorderedTree α)) :
        (node a A).insertion G = G.antidiagonal.bind fun (p : Multiset (UnorderedTree α) × Multiset (UnorderedTree α)) => Multiset.map (fun (X : Multiset (UnorderedTree α)) => node a (p.1 + X)) (insertionMultiset A p.2)
        theorem UnorderedTree.insertionMultiset_zero {α : Type u_1} (G : Multiset (UnorderedTree α)) :
        insertionMultiset 0 G = if G.card = 0 then {0} else 0
        theorem UnorderedTree.insertionMultiset_cons {α : Type u_1} (T : UnorderedTree α) (A G : Multiset (UnorderedTree α)) :
        insertionMultiset (T ::ₘ A) G = G.antidiagonal.bind fun (p : Multiset (UnorderedTree α) × Multiset (UnorderedTree α)) => (T.insertion p.1).bind fun (T' : UnorderedTree α) => Multiset.map (fun (x : Multiset (UnorderedTree α)) => T' ::ₘ x) (insertionMultiset A p.2)
        theorem UnorderedTree.insertion_mk {α : Type u_1} (t : RoseTree α) (gs : List (RoseTree α)) :
        (mk t).insertion ↑(List.map mk gs) = Multiset.map mk (t.insertion gs)

        insertion computes RoseTree.insertion on planar representatives.

        theorem UnorderedTree.insertionMultiset_mk {α : Type u_1} (hs gs : List (RoseTree α)) :
        insertionMultiset ↑(List.map mk hs) ↑(List.map mk gs) = Multiset.map (fun (L : List (RoseTree α)) => ↑(List.map mk L)) (RoseTree.insertionForest hs gs)

        insertionMultiset computes RoseTree.insertionForest on planar representatives.

        theorem UnorderedTree.insertionMultiset_zero_left_of_ne_zero {α : Type u_1} (G : Multiset (UnorderedTree α)) (h : G ≠ 0) :
        theorem UnorderedTree.insertionMultiset_singleton {α : Type u_1} (T : UnorderedTree α) (G : Multiset (UnorderedTree α)) :
        insertionMultiset {T} G = Multiset.map (fun (x : UnorderedTree α) => {x}) (T.insertion G)
        theorem UnorderedTree.insertionMultiset_card_eq {α : Type u_1} (A B : Multiset (UnorderedTree α)) {F : Multiset (UnorderedTree α)} (h : F ∈ insertionMultiset A B) :
        F.card = A.card
        theorem UnorderedTree.insertionMultiset_singleton_value {α : Type u_1} (T : UnorderedTree α) (B : Multiset (UnorderedTree α)) {F : Multiset (UnorderedTree α)} (h : F ∈ insertionMultiset {T} B) :
        ∃ (T' : UnorderedTree α), F = {T'} ∧ T'.value = T.value
        theorem UnorderedTree.exists_eq_singleton_node_of_mem_insertionMultiset {α : Type u_1} {a : α} {A B G : Multiset (UnorderedTree α)} (h : {node a G} ∈ insertionMultiset A B) :
        ∃ (F : Multiset (UnorderedTree α)), A = {node a F}

        Grafting into A gives a single tree with root a only if A is one.

        theorem UnorderedTree.insertionMultiset_antidiagonal {α : Type u_1} (A G : Multiset (UnorderedTree α)) :
        (insertionMultiset A G).bind Multiset.antidiagonal = A.antidiagonal.bind fun (pa : Multiset (UnorderedTree α) × Multiset (UnorderedTree α)) => G.antidiagonal.bind fun (pg : Multiset (UnorderedTree α) × Multiset (UnorderedTree α)) => insertionMultiset pa.1 pg.1 ×ˢ insertionMultiset pa.2 pg.2

        Splits of an output forest are splits of the host and of the guests, each guest following its host.

        theorem UnorderedTree.insertionMultiset_add_host {α : Type u_1} (A B C : Multiset (UnorderedTree α)) :
        insertionMultiset (A + B) C = C.antidiagonal.bind fun (p : Multiset (UnorderedTree α) × Multiset (UnorderedTree α)) => Multiset.map (fun (x : Multiset (UnorderedTree α) × Multiset (UnorderedTree α)) => x.1 + x.2) (insertionMultiset A p.1 ×ˢ insertionMultiset B p.2)

        Grafting into a disjoint union splits the guests between the two parts.

        The Grossman–Larson product #

        def UnorderedTree.productMultiset {α : Type u_1} (F G : Multiset (UnorderedTree α)) :
        Multiset (Multiset (UnorderedTree α))

        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
          @[simp]
          theorem UnorderedTree.productMultiset_zero_right {α : Type u_1} (F : Multiset (UnorderedTree α)) :
          productMultiset F 0 = {F}
          @[simp]
          theorem UnorderedTree.productMultiset_zero_left {α : Type u_1} (G : Multiset (UnorderedTree α)) :
          productMultiset 0 G = {G}
          theorem UnorderedTree.card_le_of_mem_productMultiset {α : Type u_1} {F G W : Multiset (UnorderedTree α)} (h : W ∈ productMultiset F G) :
          F.card ≤ W.card
          theorem UnorderedTree.insertionMultiset_singleton_node {α : Type u_1} (a : α) (A B : Multiset (UnorderedTree α)) :
          insertionMultiset {node a A} B = Multiset.map (fun (F : Multiset (UnorderedTree α)) => {node a F}) (productMultiset A B)

          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.

          theorem UnorderedTree.productMultiset_bind_antidiagonal {α : Type u_1} (A B : Multiset (UnorderedTree α)) :
          (productMultiset A B).bind Multiset.antidiagonal = (A.antidiagonal ×ˢ B.antidiagonal).bind fun (pq : (Multiset (UnorderedTree α) × Multiset (UnorderedTree α)) × Multiset (UnorderedTree α) × Multiset (UnorderedTree α)) => productMultiset pq.1.1 pq.2.1 ×ˢ productMultiset pq.1.2 pq.2.2

          Splitting the forests of A ⋆ B is splitting A and B and multiplying the parts.