Orbits of centralizers |

So in particular Young subgroups are compatible." iÎn:C_{bar (G)}(i)\\nconsists of intervals ofn.

Proof: We shall inductively construct a suitableLemma:For each subgroupP£Sthere exist_{n}pÎSsuch that_{n}pPpis compatible. For short: each subgroup^{-1}PofSis compatible up to conjugation._{n}

The basis of the induction is trivial sincepC_{P}(i)p^{-1}=C_{pPp-1}(pi).

In order to carry out the inductive step we assume that we have managed to constructp_{0}C_{P}(0)p_{0}^{-1}=C_{p0Pp0-1}(p_{0}0) =C_{p0Pp0-1}(0).

eachQ:=p_{i}...p_{1}Pp_{1}^{-1}...p_{i}^{-1},

such thatp_{i+1}ÎÅ_{i}S_{wi}

as well asp_{i+1}C_{Q}(i+1)p_{i+1}^{-1}=C_{pi+1Qpi+1-1}(i+1)

for eachC_{pi+1Qpi+1-1}(j)\\nconsists of intervals,

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:

Let us considerw^{(i)}_{1}={1},...,w^{(i)}_{i}={i},...,w^{(i)}_{t(i)}.

while" s<k:c(f¯w^{(i)}_{s})=c(g¯w^{(i)}_{s}),

c(f¯w^{(i)}_{k}) not =c(g¯w^{(i)}_{k}).

Proof:Lemma:Ifwis content critical for^{(i)}_{k}fandf', then we have, for eachsÎC, that_{bar (G)}(i)f¯w^{(i)}_{1}È...Èw^{(i)}_{k}not =f' o s¯w^{(i)}_{1}È...Èw^{(i)}_{k}.

Note that *w ^{(i)}_{1},...,w^{(i)}_{i}* are one element orbits, so

and we say that" xÎX:f(x)£g(x), for short: f£_{X}g,

This will be abbreviated by$x_{0}ÎX:f(x_{0})<g(x_{0}).

f<_{X}g.

Proof: TakeLemma:Letp,rÎbar (G)andwbe content critical for^{(i)}_{k}f:= fand_{l}o pf':=f, while we put_{l}o r. Now, ifm:=w^{(i)}_{1}È...Èw^{(i)}_{k-1}then the following is true:f¯m=f'¯m, and f<_{w(i)k}f',f£C_{bar (G)}(i)(f)Þf'£C_{bar (G)}(i)(f').

Moreover we assume thatf o s¯m=f' o s¯m.

which proves the statement.f o s¯w^{(i)}_{k}<f' o s¯w^{(i)}_{k},

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:

Proof: SinceLemma:Iff o s<f, so that there exists aj<nsuch thatwe put" x<j:f(sx)=f(x), while f(sj)>f (j),Then, for eachy:=max{sx | x<jÙf(sx)<m}, and z:=max{j,sj,y}.f'Îwithm^{n}_{l}f'¯the following is true:z=f¯zf' o s<f'.

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

- If, for this
*x<j*, we had*f o s(x)<m*, then, as*x*and*sxÎ*:__z__

a contradiction.*f' o s(x)=f o s(x)=f o s(x)=f (x)=f'(x),* - On the other hand, if
*f o s(x)=m*, then*xÎ*gives__z__

which is a contradiction, too.*m=f'(x)=f(x)=f o s(x),*

Corollary:Assumep,sandzas in the lemma, and suppose that the restrictions offandf'satisfyf'¯. Then alsoz=f¯zf'is not a canonical representative of its orbit. The lexicographically next candidatef'satisfiesf' (z)>f(z).

harald.fripertinger@kfunigraz.ac.at,

last changed: August 28, 2001

Orbits of centralizers |