18 GENERALIZATIONS O F TH E PERRON-FROBENIUS THEORE M

LEMMA

3.8. Assume that S = {pi,P2, • • • ?P/c}5 where 1 pi n for 1 i k

and pi 7^ pj for 1 i j k. Let BPi be subsets of E = {j | 0 j n — 1} with

|BPi | = Pi. If there is an integer r such that

k

^Tpj rn,

3 = 1

then there exist r + 1 integers I ji J2 ' - jr+i k such that

r+ 1

n^j^0-

2 = 1

Furthermore, if r = k — 1,

k k

\f)BPi\Y,Pj-(k-l)n.

2 = 1

j=l

PROOF. Let \j; : ^ ~* {01} denote the characteristic function of BPj, i.e.,

Xj(q) = 1 if q e Bp. and Xj(q) = 0 if q e Tl\BPj. For E i C E define

k

fc(Ei) :=rnaxY]xj(4)

J = l

and for i 1

fc

^ := {? G E | 5^Xi((7) = *i}, where k{ = fc(E \ n } -

1

^ ) -

i = i

If an integer s is chosen such that ks r and fcs+i r,

A; k k

j = l J ^ I Q G S 9 € E j = l

x;^ii+»-(n-x;M-

So

s k

Y,{ki-r)\Li\

Y^Pj~rn'

2=1 j = l

Prom this identity it follows that there exists an ZQ such that \Li0\ ^ 0. This proves

the first part of the lemma. For the second part observe that if r = k — 1 then s = 1

and we have

k k

|Q BpJ^Lxl $,--(A;-l)n.

2 = 1

J = l

D