The Garsia-Milne bijection |

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:

and as an immediate consequence, for each natural numberm ÎM_{s}ÈM^{-}Þs^{*}(m) ÎN^{+}, n ÎN^{+}\N_{t}Þt^{*}(n) ÎM^{-},

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

We now prove the existence of( t^{*}s^{*})^{k+1}(m) ÎM^{-}, and s^{*}( t^{*}s^{*})^{k+1}(m) ÎN^{+}.

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

and hence also (assumings^{*}( t^{*}s^{*})^{k(m)}(m)= s^{*}( t^{*}s^{*})^{k(m')}(m'),

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

since otherwise we hads^{*}( t^{*}s^{*})^{j}(m') ÎN_{t},

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

The Principle of Inclusion and Exclusion yieldsA_{I}:= Ç_{i ÎI}A_{i},B_{I}:= Ç_{i ÎI}B_{i}, A^{*}:=A \È_{i Î n}A_{i},B^{*}:=B \È_{i Î n}B_{i}.

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

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

Then the Garsia-Milne construction in fact allows us to sharpen the identityf_{I}:A_{I}-> B_{I}.

since we need only putg:A^{*}-> B^{*},

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

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

and the involutionsf:M -> N :(a,I) -> ( f_{I}(a),I),

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@kfunigraz.ac.at,

last changed: August 28, 2001

The Garsia-Milne bijection |