ExercisesThe involution principleThe Principle of Inclusion and ExclusionThe Garsia-Milne bijection

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 bijection We assume that
are disjoint decompositions of the finite sets M and N, that f:M -> N is a sign-preserving bijection, and that sÎSM, tÎSN are sign-reversing involutions such that Ms ÍM+, Nt ÍN+. Then the following mapping is a bijection:
g:Ms -> Nt :m -> s*( t* s*)k(m)(m),
k(m):= min{k ÎN | s*( t* s*)k(m) ÎNt }, s*:= fs, t*:= f-1 t.

Proof: Easy checks give the following implications:

m ÎMsÈM- Þs*(m) ÎN+, n ÎN+ \NtÞt*(n) ÎM-,
and as an immediate consequence, for each natural number k:
s*( t* s*)k(m) ÎN+ \Nt
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 ÎMs. If k(m) does not exist, then the implications mentioned above yield that s*( t* s*)k(m) ÎN+ \Nt, for each natural k. But this set is supposed to be finite. Hence there would be i,j ÎN, i not =j, such that s* ( t* s*)j(m)= s*( t* s*)i(m), and thus (assume j>i): ( t* s*)j-i(m)=m ÎMs, a contradiction to the earlier implications since Ms ÍM+.

Finally we mention that g is injective for the following reason: Assume m,m' ÎMs, for which g(m)= g(m'). They satisfy

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 ÎMs.
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') ÎNt,
since otherwise we had ( t* s*)k(m')-k(m)(m') ÎM-. This contradicts to the minimality of k(m').

An application to certain inclusion-exclusion situations runs as follows. Consider two families A:= {A1, ...,An } and B:= {B1, ...,Bn } of subsets of two finite sets A and B. For each I Í n we put

AI:= Çi ÎI Ai,BI:= Çi ÎIBi, A*:=A \Èi Î nAi,B*:=B \Èi Î nBi.
The Principle of Inclusion and Exclusion yields
| A* | = åI Í n(-1) | I | | AI | , | B* | = åI Í n (-1) | I | | BI | .
In the case when | AI | = | BI | , for each I Í n, these two families A and B are called sieve-equivalent , a property which implies | A* | = | B* | .

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

fI :AI -> BI.
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 ÎAi }, M+:= {(a,I) | | I | even },
N:= {(b,I) | b ÎB, " i ÎI:b ÎBi }, N+:= {(b,I) | | I | even }.
A sign preserving bijection is
f:M -> N :(a,I) -> ( fI(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' Principle If M=M+ DOTCUP M- is a disjoint decomposition of the finite set M, and s, tÎSM are sign-reversing involutions such that Ms,Mt ÍM+, then each orbit of G:= ás, tñ either consists of a fixed point of G alone, or it contains exactly one fixed point of s and exactly one fixed point of t, or it contains neither a fixed point of s nor a fixed point of t. This means in particular that there is a canonical bijection between Ms and Mt, namely the g that maps m ÎMs onto the fixed point of t that lies in the orbit G(m) of m.

last changed: August 28, 2001

ExercisesThe involution principleThe Principle of Inclusion and ExclusionThe Garsia-Milne bijection