by Cases 1 and 2 and Step 2, this is also the last cycle of sr under TTC(Q). Hence,
sr ∈ V (Q, l) and sr ∈ V (Qr, l), and (9) holds trivially.
Case 4: σ(Q, ir) < σ(Qr , ir) < l. From the proof of Case 3, sr ∈ V (Q, l) and sr ∈
V (Qr, l). Hence, (9) holds trivially.
Case 5: σ(Qr, ir) = l ≤ σ(Q, ir). Since σ(Qr, ir) = σ(Qr, sr) + 1, F(Qr, l - 1, sr) is the
last cycle of sr under T T C(Qr). By Case 1, this is a cycle of sr under TTC(Q). In fact,
by Case 1 and Step 2, this is also the last cycle of sr under TTC(Q). Hence, sr ∈ V (Q, l)
and sr ∈ V (Qr, l), and (9) holds trivially.
Case 6: σ(Qr, ir) ≤ σ(Q, ir) and l > σ(Qr, ir). From the proof of Case 5, sr ∈ V (Q, l)
and sr ∈ V(Qr,l). Hence, (9) holds trivially. □□
For each school sh ∈ CS , let jh be the student to which school sh points in the last
cycle in which sh appears under TTC(Q), i.e., jh := argmaxj∈Ash (Q) fsh (j).
Step 4 For any r ∈ {1, . . . , p}, fsr (jr) < fsr (jr+1).
Suppose fsr (jr) > fsr (jr+1). From Step 3, jr ∈ Asr (Q) = Asr (Qr) and in particular,
jr = argmaxj∈Asr (Qr) fsr (j). So,
σ(Qr, jr+1) <σ(Qr,jr) =σ(Qr,sr) =σ(Qr,ir) -1. (10)
We will now prove the following claim to complete the proof of this step.
Claim: σ(Qr, ir) ≤ σ(Qr, jr+1).
The claim yields a contradiction to (10). Hence, the assumption fsr (jr) > fsr (jr+1) is
false. Note jr = jr+ι. So, f3r(jr) < f3r(jr+ι). □
Proof of Claim:
Let j'*+ι be the student to which school sr+1 points in ir’s cycle under TTC(Q), i.e.,
e(Q, σ(Q, ir), sr+1) = jr+1. We make the following two observations (O1 and O2).
O1. σ(Qr,jr*+ι) ≥ σ(Qr,ir).
[Proof: Suppose σ(Qr , jr+1) < σ(Qr, ir).
Assume σ(Qr, ir) ≤ σ(Q, ir). Denote yr = σ(Qr, ir). From Lemma B.3(a), V(Q, yr) =
V(Qr,yrr). Bydefinitionof jr+1, jr+1 ∈ V(Q,yr). However, by assumption, σ(Qr, jr+1)
< yr, and hence, jr+1 ∈ V(Qr,yr) = V(Q,yr), a contradiction.
So, σ(Q,ir) < σ(Qr,ir). Also note that y := σ(Q,ir) ≤ σ(Qr, jr+1) (otherwise, by
Lemma B.3(a), jr+1 ∈ V(Q,y), contradicting the definition of jr+1). By Lemma
42
More intriguing information
1. The name is absent2. Implementation of Rule Based Algorithm for Sandhi-Vicheda Of Compound Hindi Words
3. Higher education funding reforms in England: the distributional effects and the shifting balance of costs
4. Personal Income Tax Elasticity in Turkey: 1975-2005
5. Constrained School Choice
6. Structural Breakpoints in Volatility in International Markets
7. The name is absent
8. DEMAND FOR MEAT AND FISH PRODUCTS IN KOREA
9. Errors in recorded security prices and the turn-of-the year effect
10. A Unified Model For Developmental Robotics