The Garsia-Milne bijection |

In situations where *two involutions* act we can use the following
result
which allows to replace certain identities of orders by bijections:

The Garsia-Milne bijectionWe assume thatare disjoint decompositions of the finite setsM=M^{+}DOTCUP M^{-}, N=N^{+}DOTCUP N^{-}MandN, thatf:M -> Nis a sign-preserving bijection, and thatsÎSare sign-reversing involutions such that_{M}, tÎS_{N}M. Then the following mapping is a bijection:_{s}ÍM^{+}, N_{t}ÍN^{+}whereg:M_{s}-> N_{t}:m -> s^{*}( t^{*}s^{*})^{k(m)}(m),k(m):= min{k ÎN| s^{*}( t^{*}s^{*})^{k}(m) ÎN_{t}}, s^{*}:= fs, t^{*}:= f^{-1}t.

Proof: Easy checks give the following implications:

m ÎM_{s}ÈM^{-}Þs^{*}(m) ÎN^{+}, n ÎN^{+}\N_{t}Þt^{*}(n) ÎM^{-},

and as an immediate consequence, for each natural number *k*:

s^{*}( t^{*}s^{*})^{k}(m) ÎN^{+}\N_{t}

implies that

( t^{*}s^{*})^{k+1}(m) ÎM^{-}, and s^{*}( t^{*}s^{*})^{k+1}(m) ÎN^{+}.

We now prove the existence of *k(m)* indirectly.
Consider *m ÎM _{s}*. If

Finally we mention that
* g* is injective for the following reason:
Assume *m,m' ÎM _{s}*, for which

s^{*}( t^{*}s^{*})^{k(m)}(m)= s^{*}( t^{*}s^{*})^{k(m')}(m'),

and hence also (assuming *k(m')-k(m) ³0*)

( t^{*}s^{*})^{k(m')-k(m)}(m')=m ÎM_{s}.

Thus either *k(m')=k(m)*, which is equivalent to *m=m'*, or there exists a
*j<k(m')-k(m)* such that

s^{*}( t^{*}s^{*})^{j}(m') ÎN_{t},

since otherwise we had *( t ^{*} s^{*})^{k(m')-k(m)}(m') ÎM^{-}*.
This contradicts to the minimality of

An application to certain inclusion-exclusion situations runs as follows.
Consider two families * A:= {A _{1}, ...,A_{n} }* and

A_{I}:= Ç_{i ÎI}A_{i},B_{I}:= Ç_{i ÎI}B_{i}, A^{*}:=A \È_{i Î n}A_{i},B^{*}:=B \È_{i Î n}B_{i}.

The Principle of Inclusion and Exclusion yields

| A^{*}| = å_{I Í n}(-1)^{ | I | }| A_{I}| , | B^{*}| = å_{I Í n}(-1)^{ | I | }| B_{I}| .

In the case when * | A _{I} | = | B_{I} | *, for each

Now we assume that this holds and that furthermore we are given,
for each *I Í n*, a bijection

f_{I}:A_{I}-> B_{I}.

Then the Garsia-Milne construction in fact allows us to sharpen the identity
* | A ^{*} | = | B^{*} | * by replacing it by a bijection

g:A^{*}-> B^{*},

since we need only put

M:= {(a,I) | a ÎA, " i ÎI:a ÎA_{i}}, M^{+}:= {(a,I) | | I | even },

N:= {(b,I) | b ÎB, " i ÎI:b ÎB_{i}}, N^{+}:= {(b,I) | | I | even }.

A sign preserving bijection is

f:M -> N :(a,I) -> ( f_{I}(a),I),

and the involutions * s, t* are as
in the proof of the Principle of Inclusion and Exclusion.
Another consequence of the Garsia-Milne bijection is (exercise):

The Two Involutions' PrincipleIfM=Mis a disjoint decomposition of the finite set^{+}DOTCUP M^{-}M, ands, tÎSare sign-reversing involutions such that_{M}M, then each orbit of_{s},M_{t}ÍM^{+}G:= ás, tñeither consists of a fixed point ofGalone, or it contains exactly one fixed point ofsand exactly one fixed point oft, or it contains neither a fixed point ofsnor a fixed point oft. This means in particular that there is a canonical bijection betweenMand_{s}M, namely the_{t}gthat mapsm ÎMonto the fixed point of_{s}tthat lies in the orbitG(m)ofm.

harald.fripertinger "at" uni-graz.at | http://www-ang.kfunigraz.ac.at/~fripert/ |

UNI-Graz | Institut für Mathematik |

UNI-Bayreuth | Lehrstuhl II für Mathematik |

The Garsia-Milne bijection |