PDF Archive

Easily share your PDF documents with your contacts, on the Web and Social Networks.

Share a file Manage my documents Convert Recover PDF Search Help Contact



Brylawski 1972 THE TUTTE GROTHENDIECK RING.pdf


Preview of PDF document brylawski-1972-the-tutte-grothendieck-ring.pdf

Page 1...3 4 56714

Text preview


Vol. 2, 1972

THE Tu'vrE-GROTHENDIECK RING

379

We then say D 1 and D 2 form a bidecomposition B(S). For clarity we denote
multisets ~ ' = l st of D 1 as X~'=l st and call an irreducible element of D 1 an
indecomposable. (Note that not every two finite decompositions on the same set form
a bidecomposition. If S = {a, b} and a < b + b while b < a x a no bidecomposition is
possible.)
If D1 and D 2 a r e unique and every element of S is either indecomposable or
irreducible we say B is free. In this case the union of the D~ and D 2 morphisms forms
a unique, hence strictly finite decomposition. Series-parallel decomposition of finite
networks ([l ]) is an example of a free decomposition.
D E F I N I T I O N 2.6. A bidecomposition is distributive if it satisfies the following
axioms:
a. D1 and D z are both unique.
b. If s < X nJ= 1 sj e D 1 for some multiset {si} of elements which are irreducible
(in D2), then s is irreducible (in D2).
c. The distributivity axiom: If s < X ~ ' = I f ~ e D i ( S ) and f , < ~ ' = l h ~ e D z ( S ) for
some k e [ 1 , n], then there exist m multisets gj such that s < ~ j ~ g j e D z and, for
each j, g j < X i = k f t x hj eD i.
In the Dl-decomposition s<X~'=i st, the distributivity axiom implies that a
nontrivial D2-decomposition of some st induces a nontrivial D 2- decomposition of s.
Hence an irreducible (for D2) fully decomposes in Dt into a multiset of elements
which are both indecomposable and irreducible.
More generally, if a decomposition D~ satisfies (2.6.c) with respect to a decomposition D 2 we say D~ distributes over D 2.
PROPOSITION 2.7. I f D i and D 2 are two decompositions which obey (a), (b),
and (c) of (2.6) then they form a distributive bidecomposition.
Proof. We need only find the function f of (2.5) which forms a bidecomposition
from D i and D z. For all seS, l e t f ( s ) = ~ ' = l ki where s < ~ 7 = 1 st is a full D 2 decomposition and for each i, let ki = 2 mi where s i < ~)~,ff'=i stj is a full D I decomposition (into
irreducible )ndecomposables). Then by distributivity and uniqueness, f induces a
bidecomposition.
D E F I N I T I O N 2.8. Let D(S) be a decomposition on a set S. Then a subset S '
of S is hereditary for D(S) i f s e S ' and s < ~ s~eD imply s~eS' for all i. Similarly S'
is hereditary for a bidecomposition B(D l, Dz) if it is hereditary for D 1 and D 2. If
S'_~ S is hereditary, the full subcategory D ( S ' ) (where the objects are multisubsets
of S') is called a subdecomposition. We have a similar notion of a subbidecomposition,

B(S').