Recursion and orderly generationConstructionsTransversals of symmetry classesOrbits of centralizers

Orbits of centralizers

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

  " iÎn:Cbar (G)(i)\\n consists of intervals of n.

So in particular Young subgroups are compatible.

Lemma: For each subgroup P£Sn there exist pÎSn such that pPp-1 is compatible. For short: each subgroup P of Sn 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:


The basis of the induction is trivial since CP(0)=P and hence there is a p0ÎSn such that p0Pp0-1 has intervals as orbits. Moreover, bythe formula above,

p0CP(0)p0-1=Cp0Pp0-1(p00) =Cp0Pp0-1(0).

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

Q:=pi...p1Pp1-1 ...pi-1,

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


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

pi+1CQ(i+1)pi+1-1=Cpi+1Qpi+1-1 (i+1)

as well as

Cpi+1Qpi+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 Cbar (G)(i) as follows:


Let us consider contents of restrictions of mappings f,gÎmnl to these orbits. We call w(i)k,k<t(i), content critical for f and g, if and only if

" s<k:c(f¯w(i)s)=c(g¯w(i)s),


c(f¯w(i)k) not =c(g¯w(i)k).
Lemma: If w(i)k is content critical for f and f', then we have, for each sÎCbar (G)(i), that
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 f ¯w(i)s and of f' o s¯w(i)s are the same, this also holds for w(i)k. Thus, by assumption, w(i)k is content critical also for f and f'. This proves the statement.

Note that w(i)1,...,w(i)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ÎCbar (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(i)1È...Èw(i)k. The next step will therefore be a discussion of content critical orbits. Let us say that fÎmn lies below gÎmn 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


This will be abbreviated by

f<X g.
Lemma: Let p,rÎbar (G) and w(i)k be content critical for f:= fl o p and f':=fl o r, while we put m:=w(i)1È...Èw(i)k-1. Now, if
f¯m=f'¯m, and f<w(i)kf',
then the following is true:
f£Cbar (G)(i)(f)Þf'£Cbar (G)(i)(f').

Proof: Take sÎCbar (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(i)k<f'¯w(i)k so that there exists an x0Îw(i)k for which f(x0) <f'(x0). Since y:=s-1(x0)Îw(i)k we have f(s(y))<f'(s(y)), and hence

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: 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'Îmnl 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:

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 "at"
UNI-Graz Institut für Mathematik
UNI-Bayreuth Lehrstuhl II für Mathematik
last changed: January 19, 2005

Recursion and orderly generationConstructionsTransversals of symmetry classesOrbits of centralizers