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. Stable Distributions2. The name is absent
3. The name is absent
4. The name is absent
5. The name is absent
6. Computational Experiments with the Fuzzy Love and Romance
7. Empirically Analyzing the Impacts of U.S. Export Credit Programs on U.S. Agricultural Export Competitiveness
8. Using Surveys Effectively: What are Impact Surveys?
9. The name is absent
10. The name is absent