B.3(b,c), j*+1 ∈ P(Qr,y,ir). Hence, σ(Qr, j*+1) ≥ y = σ(Qr,ir). Again a contra-
diction. So, σ(Qr,j*+1) ≥ σ(Qr, ir).]
O2. For all i ∈ A^(Qr) with f^‰) ≤ f^(i), σ(Qr,i) ≥ σ(Qr,j^).
Suppose jr+ι ∈ Asr+ι(Qr). Note fs^(jr*+ι) ≤ fs^(jr+ι). From O2 (with i = jr+ι) and
O1, σ(Qr,jr+ι) ≥ σ(Qr,j^ ≥ σ(Qr,ir).
Suppose now jr+1 ∈ Asr+1 (Qr). Assume σ(Qr, jr+1) < σ(Qr, ir). Then,
jr+1 = ir. (11)
We consider two cases.
Case 1: σ(Qr, ir) ≤ σ(Q, ir).
Then, σ(Qr, jr+1) < min{σ(Qr, ir), σ(Q, ir)}. From Lemma B.3(a) it follows that σ(Q, jr+1)
= σ(Qr, jr+1). So,
σ(Q, jr+1) <σ(Q,ir). (12)
However, under TTC(Q), ir is in a cycle with sr+1 and jr+1 is in the last cycle of sr+1.
So, σ(Q, jr+1) ≥ σ(Q, ir), a contradiction to (12).
Case 2: σ(Q, ir) < σ(Qr, ir).
If σ(Qr, jr+1) < σ(Q, ir), then σ(Qr, jr+1) < min{σ(Qr, ir), σ(Q, ir)} which yields the
same contradiction as in Case 1. Therefore, σ(Q, ir) ≤ σ(Qr, jr+1).
From Observation B.1 and the assumption that σ(Qr, jr+1) < σ(Qr, ir) it follows that
for each l ≤ σ(Qr, jr+1), jr+1 ∈/ P(Qr, l, ir). From (11) and Lemma B.7 it follows that for
each l with σ(Q, ir) ≤ l ≤ σ(Qr, jr+1), F (Q, l, jr+1) = F (Qr, l, jr+1) (as directed paths).
So, by taking l = σ(Qr, jr+1), we obtain that jr+1’s cycle under TTC(Q) is the same as
under TTC(Qr). In particular, jr+1 ∈ Asr+1 (Qr), a contradiction.
Since both cases give a contradiction we conclude that σ(Qr,jr+1) ≥ σ(Qr,ir). □
Step 5 There is an X -cycle.
We can assume, without loss of generality, that among the students in {j1 , . . . , jp} student
j1 is (one of) the last one(s) to be assigned to a school under TTC(Q), i.e.,
σ(Q, j1) ≥ σ(Q,jr) for any r ∈ {1, . . . ,p}. (13)
Suppose fs2 (j1) < fs2 (j2). By definition of j2, school s2 points to student j2 in the
last, qs2 -th, cycle of s2 under TTC(Q), which o ccurs at step σ(Q, s2). Hence, j1 ∈
43
More intriguing information
1. DISCUSSION: ASSESSING STRUCTURAL CHANGE IN THE DEMAND FOR FOOD COMMODITIES2. Optimal Private and Public Harvesting under Spatial and Temporal Interdependence
3. Public infrastructure capital, scale economies and returns to variety
4. Evolutionary Clustering in Indonesian Ethnic Textile Motifs
5. The demand for urban transport: An application of discrete choice model for Cadiz
6. The Role of Land Retirement Programs for Management of Water Resources
7. The name is absent
8. Review of “The Hesitant Hand: Taming Self-Interest in the History of Economic Ideas”
9. Fighting windmills? EU industrial interests and global climate negotiations
10. Input-Output Analysis, Linear Programming and Modified Multipliers