Stuff-for-eig

พิจารณาการเดินทางจาก u ไป t ให้ d(u,t) แทนระยะทางจาก u ไป t ใน base graph

case 1: ถ้ามีเส้นเชื่อมกระโดดที่กระโดดจาก u ไป w ใน D(u,t) ที่ $d(u,w)>=c\cdot d(u,t)$, สำหรับบาง c เราจะได้ว่า d(w,t) จะลดลงจาก d(u,t) มาก ดังนั้น case นี้น่าจะจัดการได้แล้ว

case 2: สมมติว่าไม่มีกรณีข้างต้น:

สำหรับระยะทาง r ใด ๆ ให้ Ball(u,r) แทน ball ที่มีจุดศูนย์กลางเป็น u รัศมี r

ให้ $Z=c\cdot d(u,t)$ แบ่ง Ball(u,Z) ออกเป็น layer ตามระยะทางจาก u

สำหรับเซ็ต U ใด ๆ ให้ P(u,U) = Pr[มีเส้นเชื่อมกระโดดจาก u ไปบางโหนดในเซ็ต U]

ให้ $Y=c'\cdot Z$ สำหรับบาง constant $0<c'<1$

(A.1) สมมติว่า P(u,D(u,t)) มีค่ามากกว่าค่าคงที่บางค่า (assumption นี้ต้องมาจัดการต่อ)

Goal: จะแสดงว่ามีความน่าจะเป็นมากพอที่จะมีเส้นเชื่อมกระโดดจาก u ไป w ที่ $d(w,t)\leq \alpha d(u,t)$ สำหรับค่าคงที่ $\alpha$ บางค่า

พิจารณา $p=P(u,Ball(u,Y)\cap D(u,t))$ และ $q=P(u,D(u,t))-P(u,Ball(u,Y)\cap D(u,t))$

แนวทาง: พิจารณา $|Ball(u,Y)\cap D(u,t)|$ กับ $|(Ball(u,Z)-Ball(u,Y))\cap D(u,t)|$