Printer Friendly

Dendriform structures for restriction-deletion and restriction-contraction matroid Hopf algebras.

We endow the set of isomorphism classes of matroids with a new Hopf algebra structure, in which the coproduct is implemented via the combinatorial operations of restriction and deletion. We also initiate the investigation of dendriform coalgebra structures on matroids and introduce a monomial invariant which satisfy a convolution identity with respect to restriction and deletion.

Keywords: matroids, combinatorial Hopf algebras (CHA), dendriform coalgebras, matroid polynomials

1 Introduction

It is widely acknowledged that major recent progress in combinatorics stems from the construction of algebraic structures associated to combinatorial objects, and from the design of algebraic invariants for those objects. For over three decades, numerous Hopf algebras with distinguished bases indexed by families of permutations, words, posets, graphs, tableaux, or variants thereof, have been brought to light (see, for example, [6] and references within). The study of such combinatorial Hopf algebras (a class of free or cofree, connected, finitely graded bialgebras thoroughly characterized by Loday and Ronco [9]) has grown into an active research area; many connections with other mathematical domains and, perhaps more surprisingly, to theoretical physics (see, for example, [14, 15] and references therein) have been uncovered and tightened.

Since Schmitt's pioneering work [13], matroids have also been the subject of algebraic structural investigations, though to a much lesser extent than other familiar combinatorial species. In the present paper, we aim to carry the study of Hopf algebras on matroids one step forward by providing an alternative coproduct on matroids and by exploring their dendriform structures.

Let us now outline the paper's contents. After a short reminder of the basic theory of matroids and a review of Schmitt's restriction-contraction Hopf algebra (section 2), we define a new coproduct, relying on two standard operations on matroids, namely restriction and deletion, and show that the set of isomorphic classes of matroids can be endowed with a new commutative and cocommutative Hopf algebra structure, different from the one introduced by Schmitt (section 3). We then prove that Schmitt's coproduct as well as ours can be adequately split into two pieces so as to give rise to two dendriform coalgebras (section 4). To the best of our knowledge, it is the first time that such an analysis has been carried out for matroids. Finally, we define a polynomial invariant of matroids which satisfy an identity which is the restrictiondeletion analog of the more classical convolution identity satisfied by the Tutte p olynomial for matroids (section 5). Although that polynomial turns out to be a monomial, its definition exemplifies the usefulness of the theory of Hopf algebra characters in our context.

2 Matroid theory; a restriction-contraction CHA

2.1 Matroid theory reminder

In this subsection we recall the definition and some basic properties of matroids (see, for example, J. Oxley's book [11] or review article [12]).

Definition 2.1 A matroid M is a pair (E, I) consisting of a finite set E and a collection of subsets of E satisfying the following set of axioms: I is non-empty, every subset of every member of I is also in I and, finally, if X and Y are in I and |X| = |Y| + 1, then there is an element x in X - Y such that Y [union] {x} is in I.

One calls the set E the ground set. The elements of the set I are the independent sets of the matroid. A subset of E that is not in I is called dependent.

A particular class of matroids is the graphic matroids (or cyclic matroids), for whom the ground set is the set of edges of the graph and for whom the collection of independent sets is given by the sets of edges which do not contain all the edges of a cycle of the graph.

Let E be an n-element set and let I be the collection of subsets of E with at most r elements, 0 [less than or equal to] r [less than or equal to] n. The pair (E, I) is a matroid - the uniform matroid [U.sub.r,n]. The smallest (with respect to the cardinal of the edge set) non-graphic matroid is [U.sub.2,4].

The bases of a matroid are the maximal independent sets of the respective matroid. Note that bases have all the same cardinality. By relaxing this condition one then has delta-matroids [1].

Let M = (E, I) be a matroid and let B = {B} be the collection of bases of M. Let B* = {E - B : B [member of] B}. Then B* is the collection of bases of a matroid M* on E, the dual of M.

Let M = (E, I) be a matroid. The rank r (A) of A [[subset].bar] E is given by the following formula:

r(A) = max{|B| s.t. B [member of] I, B [subset] A} . (1)

Lemma 2.2 (Lemma 1.3.1 [11]) The rank function r of a matroid M on a set E satisfies the following condition: If X and Y are subsets of E, then

r(X [union] Y)+ r(X [intersection] Y) [less than or equal to] r(X) + r(Y). (2)

Lemma 2.3 (Proposition 1.3.5 [11]) Let M = (E, I) be a matroid with rank function r and suppose that X [[subset].bar] E. Then X is independent if and only if|X| = r(X).

Let M = (E, I) be a matroid. The element e [member of] E is a loop if and only if {e} is a minimal dependent set of the matroid. The element e [member of] E is a coloop if and only if, for any basis B, e [member of] B.

Note that loops and coloops correspond, in graph theory, to bridges and self-loops, respectively.

Let M be a matroid (E,I) and T be a subset of E. Let [I|.sub.T] be the set {I [[subset].bar] T s. t. I [member of] I}. The pair (T, [I|.sub.T]) is a matroid, which is denoted by [M|.sub.T] - the restriction of M to T.

Let I' = {I [[subset].bar] E - T : I [member of] I}. The pair (E - T,I') is again a matroid. We denote this matroid by M\T; we call this matroid the deletion of T from M.

Lemma 2.4 Let M be a matroid (E, I) and T be a subset of E. One has:

[M|.sub.T] = [M\.sub.E-T]. (3)

2.2 A restriction-contraction matroid Hopf algebra

In this subsection we recall the restriction-contraction matroid Hopf algebra introduced in [13] (see also [2] for details).

Let us first give the following definition:

Definition 2.5 Let [M.sub.1] = ([E.sub.1],[I.sub.1]) and [M.sub.2] = ([E.sub.2],[I.sub.2]) be two matroids s. t. [E.sub.1] and [E.sub.2] are disjoint. Let [M.sub.1] [direct sum] [M.sub.2] := ([E.sub.1] [union] [E.sub.2], {[I.sub.1] [union] [I.sub.2] : [I.sub.1] [member of] [I.sub.1], [I.sub.2] [member of] [I.sub.2]}). Then [M.sub.1] [direct sum] [M.sub.2] is a matroid - the direct sum of [M.sub.1] and [M.sub.2].

If a matroid N is obtained from a matroid M by any combination of restrictions and contractions or deletions, we call the matroid N a minor of M. We write that a family of matroids is minor-closed if it is closed under formation of minors and direct sums. If M is a minor-closed family of matroids, we denote by M the set of isomorphic classes of matroids belonging to M. Direct sums induce a product on M (see [13] for details). We denote by k(M) the monoid algebra of M. over some commutative ring k with unit.

One has

Proposition 2.6 (Proposition 2.1 of [2]) If M is a minor-closed family of matroids then k(M) is a coalgebra, with coproduct [DELTA] and counit e respectively determined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4)

I 1, if E =0, and by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for all M = (E, I) [member of] M. If furthermore, the family M is closed under formation of direct sums, then k(M) is a Hopf algebra, with product induced by direct sum.

In the rest of the paper, we follow [2] and, by a slight abuse of notation, we denote in the same way a matroid and its isomorphic class, since the distinction will be clear from the context (as it is already in Proposition 2.6). This is the same for the restriction-deletion matroid Hopf algebra that we will introduce in the following section.

The empty matroid (or [U.sub.0,0]) is the unit of this Hopf algebra and is denoted by 1.

Example 2.7 (Example 2.4 of [2]) Let M = [U.sub.k,n] be a uniform matroid with rank k. Its coproduct is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

3 A restriction-deletion matroid Hopf algebra

Let us define the following restriction-deletion map:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (5)

Example 3.1 One has

1) If 2k [less than or equal to] n,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (6)

2) If n < 2k,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (7)

One has:

Lemma 3.2 (Proposition 3.1.26 of [11]) Let M = (E, I) be a matroid.

1) Let X' be a subset of X which is a subset of the ground set E. One has

(M | X) | X' = M | X', (8a)

(M | X)|X' = M | (X - X'). (8b)

2) Let X and Y be subsets of E such that X and Y are disjoint, one has

(M|X) | Y = M | Y, (9a)

(M|X)|Y = M|(X [union] Y). (9b)

Proof: These identities follow directly from the definitions of restriction and deletion for matroids (see previous section). []

Proposition 3.3 The coproduct in (5) is coassociative.

Proof: Let M = (E, I) be a matroid. Let us calculate the left hand side (LHS) and right hand side (RHS) of the coassociativity identity. One has

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (10)

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (11)

Equations (10) and (11) lead to the conclusion. []

Let us explicitly check the coassociativity of [[DELTA].sup.(II)] on [U.sub.2,4].

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (12)

Proposition 3.4 The coproduct in (5) is cocommutative.

Proof: Let [tau] be a map M [cross product] M [right arrow] M [cross product] M defined by [M.sub.1] [cross product] [M.sub.2] [??] [M.sub.2] [cross product] [M.sub.1]. Using Lemma 2.4, for M = (E, I) [member of] M, one has

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (13)

Proposition 3.5 k(M) is a cocommutative coalgebra with coproduct [[DELTA].sup.(II)] and counit e given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (14)

Proof: The proof follows directly from the definition (14). []

Lemma 3.6 (Proposition 4.2.23 [11]) Let [M.sub.1] and [M.sub.2] be two matroids. Let [A.sub.1] and [A.sub.2] be subset of [E.sub.1] and [E.sub.2], respectively. One then has

1) [M.sub.1] | [A.sub.1] [direct sum] [M.sub.2] | [A.sub.2] = ([M.sub.1] [direct sum] [M.sub.2]) | ([A.sub.1] [union] [A.sub.2]). (15)

2) [M.sub.1]\[A.sub.1] [direct sum] [M.sub.2]\[A.sub.2] = ([M.sub.1] [direct sum] [M.sub.2])\([A.sub.1] [union] [A.sub.2]). (16)

Proof: One can check these identities directly from the definitions of direct sum, restriction and deletion for matroids (see again the previous section). []

Let [[direct sum].sup.[cross product]2] denote ([direct sum] [cross product] [direct sum]) [omicron] [[tau].sub.23] where [[tau].sub.23] is the map M [cross product] M [cross product] M [cross product] M [right arrow] M [cross product] M [cross product] M [cross product] M defined by [M.sub.1] [cross product] [M.sub.2] [cross product] [M.sub.3] [cross product] [M.sub.4] [??] [M.sub.1] [cross product] [M.sub.3] [cross product] [M.sub.2] [cross product] [M.sub.4].

Proposition 3.7 Let [M.sub.1] and [M.sub.2] be two matroids. One has

[[DELTA].sup.(II)]([M.sub.1] [direct sum] [M.sub.2]) =[[DELTA].sup.(II)]([M.sub.1])[[direct sum].sup.[cross product]2] [[DELTA].sup.(II)]([M.sub.2]). (17)

Proof: Lemma 3.6 leads to:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (18)

which concludes the proof. []

Let us now explicitly check this identity on the matroids [M.sub.1] = ({1,2}, {[??], {1}, {2}}) and [M.sub.2] = ({3,4, 5}, {[??], {3}, {4}, {5}}) ([U.sub.1,2] and respectively [U.sub.1,3]). One has:

[[DELTA].sup.(II)] ([M.sub.1]) = 1 [cross product] [U.sub.1,2] + 2[U.sub.1,1] [cross product][U.sub.1,1] + [U.sub.1,2] [cross product] 1. [[DELTA].sup.(II)] ([M.sub.2]) = 1 [cross product][U.sub.1,3] + 3[U.sub.1,1] [cross product][U.sub.1,2] + 3[U.sub.1,2] [cross product][U.sub.1,1] + [U.sub.1, 3] [cross product] 1. (19)

which further leads to:

[M.sub.1] [direct sum] [M.sub.2] = ({1, 2, 3,4, 5}, {[??], {1}, {2}, {3}, {4}, {5}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}}).

Thus, one gets

[[DELTA].sup.(II)] ([M.sub.1] [direct sum] [M.sub.2]) = 1 [cross product] ([U.sub.1,2] [direct sum] [U.sub.1,3]) + 2[U.sub.1,1] [cross product] ([U.sub.1,1] [direct sum] [U.sub.1,3]) + 3[U.sub.1,1] [cross product] ([U.sub.1,2] [direct sum] [U.sub.1,2]) +[U.sub.1,2] [cross product][U.sub.1,3] + 6[U.sub.2,2] [cross product] ([U.sub.1,1] [direct sum] [U.sub.1,2]) + 3[U.sub.1,2] [cross product] ([U.sub.1,2] [direct sum][U.sub.1,1]) +3([U.sub.1,2] [direct sum] [U.sub.1,1]) [cross product] [U.sub.1,2] + 6([U.sub.1,1] [direct sum] [U.sub.1,2]) [cross product] [U.sub.1,1] + [U.sub.1,3] [cross product] [U.sub.1,2] +3([U.sub.1,2] [direct sum] [U.sub.1,2]) [cross product] [U.sub.1,1] + 2([U.sub.1,1] [direct sum] [U.sub.1,3]) [cross product][U.sub.1,1] + ([U.sub.1,2] [direct sum][U.sub.1,3]) [cross product] 1 = [[DELTA].sup.(II)]([M.sub.1])[[direct sum].sup.[cross product]2] [[cross product].sup.(II)]([M.sub.2]). (20)

Proposition 3.8 The triplet (k(M), [direct sum], [[DELTA].sup.(II)]) is a commutative and cocommutative bialgebra.

Proof: The claim follows directly from Proposition 3.7 and the results above. []

The main result of this section is:

Theorem 3.9 The triplet (k(M),[direct sum], [[DELTA].sup.(II)]) is a commutative and cocommutative Hopf algebra. The antipode S of this Hopf algebra is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (21).

Proof: The bialgebra is graded by the cardinal of the ground set of matroids. Moreover, M. is connected, i. e. [M.sub.0] = k1. This leads to the conclusion. []

Let us end this section with the following example: Example 3.10 One has:

S([U.sub.3,3]) = -[U.sub.3,3] + 3[U.sub.1,1] [direct sum] [U.sub.2,2] + 3[U.sub.2,2] [direct sum] [U.sub.1,1] - 6[U.sub.1,1] [direct sum] [U.sub.1,1] [direct sum] [U.sub.1,1]. (22)

4 Dendriform matroid coalgebras

Let us first recall that a dendriform algebra [8, 9, 10, 5] is a family (A, [??], [??]) such that A is a vector space and [??], [??] are two products on A, satisfying three axioms. Dually, one has a dendriform coalgebra (C,[[DELTA].sub.[??]],[[DELTA].sub.[??]]).

Definition 4.1 (Definition 2 of [5]) A dendriform coalgebra is a family (C, [[DELTA].sub.[??]], [[DELTA].sub.[??]]) such that:

1. C is a k-vector space and one has:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (23)

2. For all a [member of] C, one has:

([[DELTA].sub.[??]] [cross product] Id) [omicron] [[DELTA].sub.[??]](a) = (Id [cross product] [[DELTA].sub.[??]] + Id eg [DELTA]y) [omicron] [[DELTA].sub.[??]](a), (24)

([[DELTA].sub.[??]] [cross product] Id) [omicron] [[DELTA].sub.[??]](a) = (Id [cross product] [[DELTA].sub.[??]]) [omicron] [[DELTA].sub.[??]](a), (25)

([[DELTA].sub.[??]] [cross product] Id + [[DELTA].sub.[??]] [cross product] Id) [omicron] [[DELTA].sub.[??]] (a) = (Id [cross product] [[DELTA].sub.[??]]) [omicron] [[DELTA].sub.[??]](a). (26)

If C is a coalgebra, one defines

[DELTA]* : C [right arrow] C [cross product] C, a [??] [DELTA]* (a) = [DELTA](a) - a [cross product] 1 - 1 [cross product] a (27)

4.1 The restriction-deletion case

Let us now define two maps on [M.sub.+] by:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (28)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (29)

If A [[subset].bar] E, then r(A) [less than or equal to] |A|. This directly leads to:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (30)

From Lemma 2.3, one can see that the coproduct [[DELTA]*.sup.(II)] in Equation (5) is split into two parts: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] sums on the dependent sets of the matroid and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] sums on the independent sets of the matroid.

Let k[(M).sub.+] be the augmentation ideal of k(M). We can now state the main result of this section:

Proposition 4.2 The triplet ([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) is a dendriform coalgebra.

Proof: Let M be the matroid (E, I). Let us first prove identity (24). Its LHS writes:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (31)

On the other hand, the RHS of identity (24) can be rewritten as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (32)

From Lemma 2.2, one has:

r(X [union] Y) [less than or equal to] r(X) + r(Y) < |X| + |Y| = |X [union] Y|. (33)

Setting X = B and X [union] Y = A in equation (32) one now gets that identity (24) holds.

Let us now prove identity (25). Its LHS writes:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (34)

The RHS of identity (25) writes:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (35)

As above, we can now set X = B and X [union] Y = A in the previous equation. One then concludes that identity (25) also holds.

Finally, identity (26) holds because of the coassociativity of [[DELTA]*.sup.(II)] and since identities (24) and (25) also hold. This concludes the proof. []

We end this section by the following remark. The triplet ([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) is not a codendriform bialgebra. Indeed, the necessary compatibilities for the dendriform coalgebra ([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) to be a codendriform bialgebra [5] write:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (36)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (37)

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. In our case, one gets the identity

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (38)

which is different of the identity (36) above.

4.2 The restriction-contraction case

As in the case of the restriction-deletion coproduct analyzed in the previous subsection, one can use the coproduct [[DELTA].sup.(I)] to define a restriction-contraction dendriform coalgebra structure.

One defines two maps on [M.sub.+] by:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (39)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (40)

One has

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (41)

One has

Proposition 4.3 The triplet ([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) is a dendriform coalgebra.

Proof: The proof of Proposition 4.2 applies for this case as well. []

This dendriform coalgebra is not a codendriform bialgebra for the same reasons as in the case of the dendriform restriction-deletion matroid coalgebra of the previous subsection.

5 A matroid polynomial

In this section we use an appropriate character of the restriction-deletion matroid Hopf algebra in order to define a certain matroid polynomial.

Definition 5.1 Let M = (E,I) be a matroid. Let A[[subset].bar]E. One defines

c(A) := #{e [member of] A | {e} [member of] I}, (42)

l(A) := #{e [member of] A | {e} [member of]I}. (43)

Example 5.2 Let M be a matroid on the ground set {1, 2,3,4} and the collection of independent sets be given by I = {[??], {1}, {2}, {3}}. One has l(E) = 3 and c(E) = 1. Let A = {1,2,4}. One then has l(A) = 2 and c(A) = 1.

Remark 5.3 For graphs, l counts the number of self-loops and c counts the number of edges which are not self-loops.

Note that the matroid of Example 5.2 is a graphic matroid, see Fig. 1. One has, as already noted above l(E) = 3 and c(E) = 1.

[FIGURE 1 OMITTED]

Remark 5.4 1) If{e} [member of] I, then M | e = [U.sup.1,1].

2) If{e} [member of] I, then M | e = [U.sub.0,1].

Let M = (E, I) be a matroid. Let us define the following polynomial:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (44)

Remark 5.5 Note that the definition above mimics the definition of the Tutte polynomial, where the role of the rank and of the nullity are played by the parameters c and l, respectively.

Example 5.6 One has:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (45)

As in [3], we now define:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (46)

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (47)

It is easy to check that these maps are infinitesimal characters of the restriction-deletion matroid Hopf algebra.

Following [3] again, we define the map:

[alpha](x, y, s, M) := exp*s{[[delta].sub.coloop] + (y - 1)[[delta].sub.loop]} * exp*s{(x - 1)[[delta].sub.coloop] + [[delta].sub.loop]}(M). (48)

Using the definition of a Hopf algebra character one can directly check that the map (48) defined above is a character.

Let us now show the relation between the map [alpha] and the polynomial in (44).

Lemma 5.7 One has

exp*{a[[delta].sub.coloop] + b[[delta].sub.loop]}(M) = [a.sup.c(M)][b.sup.l(M)]. (49)

Proof: The proof of Lemma 4.1 of [3] for the restriction-contraction matroid Hopf algebra applies for the restriction-deletion matroid Hopf algebra as well (where one takes again into consideration that the role of the rank and of the nullity are played by the parameters c and l). []

Proposition 5.8 One has

[alpha](x,y, s, M) = [s.sup.|E|] [P.sub.M](x,y). (50)

Proof: The proof of Proposition 4.3 of [3] for the restriction-contraction matroid Hopf algebra applies for the restriction-deletion matroid Hopf algebra as well (where one takes again into consideration that the role of the rank and of the nullity are played by the parameters c and l). []

One further has:

Corollary 5.9 Let M1 and M2 be two matroids. One has

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (51)

Proof: The conclusion follows directly from the definition of a Hopf algebra character and from Proposition 5.8 above. D

One then has:

[alpha](x,y,s,M) = exp* (s([[delta].sub.coloop] + (y - 1)[[delta].sub.loop])) * exp* (s(-[[delta].sub.coloop] + [[delta].sub.loop])) * exp* (s([[delta].sub.coloop] - [[delta].sub.loop])) * exp* (s((x - 1) [[delta].sub.coloop] + [[delta].sub.loop])) . (52)

One has:

Corollary 5.10 The polynomial in Equation (44) satisfies

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (53)

Proof: The proof of Corollary 4.5 of [3] applies for the polynomial P. []

Remark 5.11 The identity above is the analog of a convolution identity for the Tutte polynomial proved initially in [4] and [7]. The difference comes from replacing the matroid contraction, in the Tutte polynomial case, with the matroid deletion, in the last factor of the identity.

Note that [P.sub.M](x, y) = [P.sub.M/e](x, y) + [P.sub.M\e](x, y) where e is neither a loop nor a coloop.

Let us now give the recursive relations satisfied by the polynomial [P.sub.M](x, y).

Proposition 5.12 One has

[P.sub.M](x,y) = y[P.sub.M\e](x,y) ifeis a loop, (54)

[P.sub.M](x,y) = x[P.sub.M\e](x,y) otherwise. (55)

Proof: If e is a loop, then c(E - e) = c(E). One now has

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (56)

Similarly, if e is not a loop, one then has [P.sub.M](x, y) = x[P.sub.M\e](x, y). []

Corollary 5.13 One has

[P.sub.M](x,y) = [x.sup.c(E)][y.sup.l(E)]. (57)

Finally, one notices that [P.sub.M](x, y) = [P.sub.M]* (x, y), and [P.sub.M](x, y) [not equal to] PM* (y,x). This follows, for example, from analyzing the cases of the matroids [U.sub.0,1] = [U*.sub.1,1] and [U.sub.1,2] = [U*.sub.1,2].

Acknowledgements

The authors kindly acknowledge G. Duchamp and G. Koshevoy for discussions on positroids, discussions which have eventually led to our work on matroids.

References

[1] A. Bouchet, Greedy algorithm and symmetric matroids, Math. Program., 38 (1987) 147-159.

[2] H. Crapo and W. Schmitt, A free subalgebra of the algebra of matroids, Europ. J. Combin., 26 (2005) 1066-1085.

[3] G. Duchamp, N. Hoang-Nghia, T. Krajewski and A. Tanasa, Recipe theorem for the Tutte polynomial for matroids, renormalization group-like approach, Advances in Applied Mathematics, 51 (2013) 345-358.

[4] G. Etienne and M. Las Vergnas, External and internal elements of a matroid basis, Discrete Math., 179 (1998) 111-119.

[5] L. Foissy, Bidendriform bialgebras, trees, and free quasi-symmetric functions, J. Pure Appl. Algebra, 209 (2007) 439-459.

[6] L. Foissy, J.-C. Novelli and J.-Y. Thibon, Polynomial realizations of some combinatorial Hopf algebras, Journal of Noncommutative Geometry, 8(1) (2014) 141-162. DOI: 10.4171/JNCG/151

[7] W. Kook, V. Reiner and D. Stanton, A convolution formula for the Tutte polynomial, J. Combin. Theory Ser. B, 76 (1999) 297-300.

[8] J.-L. Loday, Dialgebras, in Dialgebras and related operads, vol. 1763 of Lecture Notes in Math., pages 7-66, Springer, 2001.

[9] J.-L. Loday and M. Ronco, Combinatorial Hopf Algebras, in Quanta of Maths, vol. 11 of Clay Math. Proc., pages 347-383, Amer. Math. Soc., 2010.

[10] J.-L. Loday and M. Ronco, Hopf algebra of planar binary trees, Adv. Math., 139 (1998) 293-309.

[11] J. Oxley, Matroid theory, Oxford Univ. Press, 1992.

[12] J. Oxley, What is a matroid?, Cubo Mat. Educ., 5 (2003) 179-218.

[13] W. Schmitt, Incidence Hopf algebras, J. Pure Appl. Algebra, 96 (1994) 299-330.

[14] A. Tanasa, Some combinatorial aspects of quantum field theory, Seminaire Lotharingien de Combinatoire, B65g (2012) [arXiv:1102.4231 [math.CO]].

[15] A. Tanasa, Combinatorial Hopf Algebras in (Noncommutative) Quantum Field Theory, Rom. J. Phys., 55 (2010) 1142 [arXiv:1008.1471 [math.CO]].

Nguyen Hoang-Nghia (1) Adrian Tanasa (234*) Christophe Tollu (1)

(1) Univ. Paris 13 Sorbonne Paris Cite, France

(2) Univ. Bordeaux, France

(3) NIPNE Magurele, Romania

(4) IUF Paris, France

received 2014-10-13, revised 2016-01-07, accepted 2016-01-07.

(*) A. T. is partially funded by the grants ANR JCJC "CombPhysMat2Tens" and PN 09 37 01 02.
COPYRIGHT 2016 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2016 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Hoang-Nghia, Nguyen; Tanasa, Adrian; Tollu, Christophe
Publication:DMTCS Proceedings
Article Type:Report
Date:Jan 1, 2016
Words:4585
Previous Article:Arithmetic completely regular codes.
Next Article:Rainbow eulerian multidigraphs and the product of cycles.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters