حل تمرین گسترگراف

من یک حل که برای سوال ۱ تمرین ۲ پیدا کردم خیلی طولانی بود:
http://math.mit.edu/~jorloff/suppnotes/suppnotes03/ls3.pdf
برای سوال ۲ تمرین ۲ هم تعداد تکرارهایی که برای همگرا شدن لازم داشت لگاریتمی بود (چون با احتمال ثابت موفقیت‌آمیز بود) ولی الگوریتم اصلی (که در سوال آمده) ضریبش نسبت مقدار ویژه‌های اول و دوم است (به ترتیب از بزرگ به کوچک).
https://en.wikipedia.org/wiki/Power_iteration#Analysis

جوک در مورد گسترگراف!

ارتباطش با گسترگراف: اون شکلی که به فیزیکدانه نشون میده. جوابش توی مبحث قدم‌زدن تصادفی هست.

کامل‌ترین جزوه‌ی تراویسان (گسترگراف)

https://people.eecs.berkeley.edu/~luca/expanders2016/index.html

اثبات قضیه‌ی آخر فصل ۳ گسترگراف تراویسان (نسخه برکلی!)

دریافت

از روی اینترنت:

https://people.eecs.berkeley.edu/~luca/expanders2016/lecture05.pdf

درس گسترگراف شایان اویس قرن

http://homes.cs.washington.edu/~shayan/courses/cse599/

درس گسترگراف در استنفورد (تراویسان)

علاوه بر درسی که در برکلی داده در استنفورد هم این را ارائه کرده است.
http://theory.stanford.edu/~trevisan/expander-online/lecture02.pdf

spectral graph theory

https://ocw.mit.edu/courses/mathematics/18-409-topics-in-theoretical-computer-science-an-algorithmists-toolkit-fall-2009/lecture-notes/

تمرین 1 نظریه طیفی گراف (ام آی تی)

https://ocw.mit.edu/courses/mathematics/18-409-topics-in-theoretical-computer-science-an-algorithmists-toolkit-fall-2009/assignments/MIT18_409F09_ps1.pdf

سایت درس اکسپندرز

http://theory.stanford.edu/~trevisan/cs359g/

https://people.eecs.berkeley.edu/~luca/expanders2016/index.html