Orbits of centralizers |

We say that *bar (G)£S _{n} * is

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

So in particular Young subgroups are compatible.

Lemma:For each subgroupP£Sthere exist_{n}pÎSsuch that_{n}pPpis compatible. For short: each subgroup^{-1}PofSis compatible up to conjugation._{n}

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_{0}C_{P}(0)p_{0}^{-1}=C_{p0Pp0-1}(p_{0}0) =C_{p0Pp0-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_{1}Pp_{1}^{-1}...p_{i}^{-1},

each *C _{Q}(j)\\n* consists of intervals, for each

p_{i+1}ÎÅ_{i}S_{wi}

such that *p _{i+1}C_{Q}(i+1)p_{i+1}^{-1}=C_{pi+1Q
pi+1-1}(p_{i+1}i+1)* has intervals as orbits.
Since the orbit

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

as well as

C_{pi+1Qpi+1-1}(j)\\nconsists 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^{(i)}_{1}={1},...,w^{(i)}_{i}={i},...,w^{(i)}_{t(i)}.

Let us consider *contents of restrictions* of mappings *f,gÎ m^{n}_{l} *
to these orbits. We call

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

while

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

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

Proof:
*s* fixes each
*w ^{(i)}_{s}* setwise, and hence the contents of

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

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

and we say that *f* lies *strictly* below *g* in *X* if *f£ _{X}g* and

$x_{0}ÎX:f(x_{0})<g(x_{0}).

This will be abbreviated by

f<_{X}g.

Lemma: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').

Proof: Take *sÎC _{bar (G)}(i)*. The assumed equality
of the restrictions to

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

Moreover we assume that *f¯w ^{(i)}_{k}<f'¯w^{(i)}_{k}* so that there exists an

f o s¯w^{(i)}_{k}<f' o s¯w^{(i)}_{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: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'.

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__

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 "at" uni-graz.at | http://www-ang.kfunigraz.ac.at/~fripert/ |

UNI-Graz | Institut für Mathematik |

UNI-Bayreuth | Lehrstuhl II für Mathematik |

Orbits of centralizers |