Algebraic Combinatorics -- Orbits of centralizers

Orbits of centralizers

Orbits of centralizers

We say that bar (G)£S_n is compatible (with the natural order on n), if and only if the following holds:

" iÎn:C_{bar (G)}(i)\\n consists of intervals of n.

So in particular Young subgroups are compatible.

Lemma: For each subgroup P£S_n there exist pÎS_n such that pPp^-1 is compatible. For short: each subgroup P of S_n is compatible up to conjugation.

Proof: We shall inductively construct a suitable p that does the appropriate conjugation. Before we start doing so we note that the following is true:

pC_P(i)p^-1=C_pPp^-1(pi).

The basis of the induction is trivial since C_P(0)=P and hence there is a p₀ÎS_n such that p₀Pp₀^-1 has intervals as orbits. Moreover, bythe formula above,

p₀C_P(0)p₀^-1=C_p₀Pp₀^-1(p₀0) =C_p₀Pp₀^-1(0).

In order to carry out the inductive step we assume that we have managed to construct p_i such that, for

Q:=p_i...p₁Pp₁^-1 ...p_i^-1,

each C_Q(j)\\n consists of intervals, for each jÎi. Consider now the subgroup C_Q(i+1) of C_Q(i), each orbit w_i+1 of which is contained in an orbit w_i of C_Q(i), and w_i is an interval. Therefore we can find

p_i+1ÎÅ_iS_{w_i}

such that p_i+1C_Q(i+1)p_i+1^-1=C_{p_i+1Q
p_i+1^-1}(p_i+1i+1) has intervals as orbits. Since the orbit {i+1} already is an interval, we can moreover assume that p_i+1(i+1)=i+1, so that in fact p_i+1 is in the centralizer of i, and hence

p_i+1C_Q(i+1)p_i+1^-1=C_{p_i+1Qp_i+1^-1} (i+1)

as well as

C_{p_i+1Qp_i+1^-1}(j)\\n consists of intervals,

for each jÎi, too, and this completes the proof.

We can therefore assume without restriction that bar (G) is compatible, and hence there is also a natural way of numbering the orbits C_{bar (G)}(i) as follows:

w⁽ⁱ⁾₁={1},...,w⁽ⁱ⁾_i={i},...,w⁽ⁱ⁾_t(i).

Let us consider contents of restrictions of mappings f,gÎmⁿ_l to these orbits. We call w⁽ⁱ⁾_k,k<t(i), content critical for f and g, if and only if

" s<k:c(f¯w⁽ⁱ⁾_s)=c(g¯w⁽ⁱ⁾_s),

while

c(f¯w⁽ⁱ⁾_k) not =c(g¯w⁽ⁱ⁾_k).

Lemma: If w⁽ⁱ⁾_k is content critical for f and f', then we have, for each sÎC_{bar (G)}(i), that
f¯w⁽ⁱ⁾₁È...Èw⁽ⁱ⁾_k not =f' o s¯w⁽ⁱ⁾₁È...Èw⁽ⁱ⁾_k.

Proof: s fixes each w⁽ⁱ⁾_s setwise, and hence the contents of f ¯w⁽ⁱ⁾_s and of f' o s¯w⁽ⁱ⁾_s are the same, this also holds for w⁽ⁱ⁾_k. Thus, by assumption, w⁽ⁱ⁾_k is content critical also for f and f'. This proves the statement.

Note that w⁽ⁱ⁾₁,...,w⁽ⁱ⁾_i are one element orbits, so f=f o p and f o s=f o p o s are identical there, so the preceding lemma means first of all that in order to carry out the minimality test, if f<f o s,sÎC_{bar (G)}(i), say, we can start from checking f(i) instead of starting from the very beginning f(1). Moreover the decision if f£f o s will be made at last by checking if f(m)<f(sm), where m=w⁽ⁱ⁾₁È...Èw⁽ⁱ⁾_k. The next step will therefore be a discussion of content critical orbits. Let us say that fÎmⁿ lies below gÎmⁿ in XÍn if and only if

" xÎX:f(x)£g(x), for short: f£_Xg,

and we say that f lies strictly below g in X if f£_Xg and

$x₀ÎX:f(x₀)<g(x₀).

This will be abbreviated by

f<_X g.

Lemma: Let p,rÎbar (G) and w⁽ⁱ⁾_k be content critical for f:= f_l o p and f':=f_l o r, while we put m:=w⁽ⁱ⁾₁È...Èw⁽ⁱ⁾_k-1. Now, if
f¯m=f'¯m, and f<_{w⁽ⁱ⁾_k}f',
then the following is true:
f£C_{bar (G)}(i)(f)Þf'£C_{bar (G)}(i)(f').

Proof: Take sÎC_{bar (G)}(i). The assumed equality of the restrictions to m yields, first of all, that also

f o s¯m=f' o s¯m.

Moreover we assume that f¯w⁽ⁱ⁾_k<f'¯w⁽ⁱ⁾_k so that there exists an x₀Îw⁽ⁱ⁾_k for which f(x₀) <f'(x₀). Since y:=s^-1(x₀)Îw⁽ⁱ⁾_k we have f(s(y))<f'(s(y)), and hence

f o s¯w⁽ⁱ⁾_k<f' o s¯w⁽ⁱ⁾_k,

which proves the statement.

Note that the last lemma turns out to be a generalization ofthe lemma if we identify the point i with the orbit {i}. Finally it should be mentioned that we can also learn from a negative result in a minimality test, which is absolutely necessary, since otherwise we would not have the slightest chance to overcome the complexity:

Lemma: If f o s<f, so that there exists a j<n such that
" x<j:f(sx)=f(x), while f(sj)>f (j),
we put
y:=max{sx | x<jÙf(sx)<m}, and z:=max{j,sj,y}.
Then, for each f'Îmⁿ_l with f'¯z=f¯z the following is true:
f' o s<f'.

Proof: Since j and sj are contained in z, we have

f' o s(j)=f'(sj)=f(sj)<f (j)=f'(j).

Hence f' o s³f' would imply the existence of an x<j such that f' o s(x)> f'(x). This leads to a contradiction:

If, for this x<j, we had f o s(x)<m, then, as x and sxÎz:
f' o s(x)=f o s(x)=f o s(x)=f (x)=f'(x),
a contradiction.
On the other hand, if f o s(x)=m, then xÎz gives
m=f'(x)=f(x)=f o s(x),
which is a contradiction, too.

Corollary: Assume p,s and z as in the lemma, and suppose that the restrictions of f and f' satisfy f'¯z=f¯z. Then also f' is not a canonical representative of its orbit. The lexicographically next candidate f' satisfies f' (z)>f(z).

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

Orbits of centralizers