Notes

Author: Samuele Giraudo
Creation: sept. 2018
Modifications: dec. 2018

== Operads on multigraphs ==

= Description of the structure =
Objects: non oriented finite multigraphs. The vertex set of all
multigraphs are bijectively labeled.

Notation: for instance,
    1,2,3|1-(1)-2,1-(1)-3,2-(2)-3
denotes the multigraph on the vertex set {1, 2, 3} and with
an edge between 1 and 2, and edge between 1 and 3, and two edges between
2 and 3.

Arity: number of vertices.
MG is not combinatorial. (An operad is combinatorial if it admits finite
dimensions arity by arity.)

Vector space MG on these objects.

Partial composition:
when G_1 and G_2 are two disjoint multigraphs,
    G_1 \circ_a G_2
is the sum of all the multigraphs G_3 obtained by replacing the vertex a
of G_1 by G_2, by adding in all possible ways edges {x_1, x_2} for all
vertices x_2 of G_2 and all vertices x_1 of G_1 adjacent to a, and by
adding for any loop on a in G_1 an edge {x_2, x'_2} between vertices
x_2 and x'_2 of G_2.

Action of the symmetric group:
classical relabeling of the vertices of the multigraphs.

Unit: multigraph with one vertex.

e(G) := number of edges of G.
e(G_1 \circ_a G_2) = e(G_1) + e(G_2)

Since there is an infinite number of multigraphs of arity n, we can work
by filtering them by their weight w(G) where
    w(G) := |G| +  e(G).
Number of multigraphs by weight:
    1, 2, 5, 14, 43, 143, 510,
(A098569)

Basis changes:
For any multigraph G, let H_G be the sum of all the multigraphs obtained
by removing an arbitrary number of edges from G.
The set of all the H_G forms a basis of MG. Nevertheless, the partial
composition on this basis is not nice (negative integer coefficients).

= Generating set =
First candidate:
    S := {1|1-(1)-1, 1,2|}
Number of graphs by weight in the suboperad generated by S:
    1, 2, 5, 14, 43, 142
Since 142 < 143, S is not a generating set. The element
    1,2,3|1-(2)-2,2-(1)-3
(the "tadpole") must be added as a generator.
Actual candidate:
    S := {1|1-(1)-1, 1,2|, 1,2,3|1-(2)-2,2-(1)-3}


= Suboperads =
The partial composition is stable on simple graphs (multigraphs with
no loop and with no multiple edges), so that the vector space SG of
simple graphs is a suboperad of MG.

Here are some suboperads of MG generated by some finite sets of
multigraphs, with their dimensions:
    {1,2|}              -> 1, 1, 1, ...
    {1,2|1-(1)-2}       -> 1, 1, 3, 15, 105, ?
    {1,2|, 1,2|1-(1)-2} -> 1, 2, 7, 37, ?

Remark: let S is a set of multigraphs. If there is no graph of arity 1
in S, then the suboperad of MG generated by S is combinatorial.