Algebraic Combinatorics -- The Garsia-Milne bijection

The 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
M=M⁺ DOTCUP M^-, N=N⁺ DOTCUP N^-
are disjoint decompositions of the finite sets M and N, that f:M -> N is a sign-preserving bijection, and that sÎS_M, tÎS_N are sign-reversing involutions such that M_s ÍM⁺, N_t ÍN⁺. Then the following mapping is a bijection:
g:M_s -> N_t :m -> s^*( t^* s^*)^k(m)(m),
where
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 k(m) does not exist, then the implications mentioned above yield that s^*( t^* s^*)^k(m) ÎN⁺ \N_t, 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^*)ⁱ(m), and thus (assume j>i): ( t^* s^*)^j-i(m)=m ÎM_s, a contradiction to the earlier implications since M_s ÍM⁺.

Finally we mention that g is injective for the following reason: Assume m,m' ÎM_s, 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 Î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 k(m').

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

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 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

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' Principle If M=M⁺ DOTCUP M^- is a disjoint decomposition of the finite set M, and s, tÎS_M are sign-reversing involutions such that M_s,M_t Í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 M_s and M_t, namely the g that maps m ÎM_s onto the fixed point of t that lies in the orbit G(m) of m.

harald.fripertinger@kfunigraz.ac.at,
last changed: August 28, 2001

The Garsia-Milne bijection