مقدار ویژه‌های گرافها

https://www.win.tue.nl/~aeb/2WF02/easyspectra.pdf

کران برای عدد رنگی گراف از روی ماتریس مجاورت آن

http://www.cs.yale.edu/homes/spielman/561/lect03-15.pdf

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

درس امین صابری هم دو تا تمرین داره.
http://web.stanford.edu/class/msande337/HW1.pdf
http://web.stanford.edu/class/msande337/HW2.pdf

تغییر فاز در گرافهای تصادفی غیریکنواخت

تغییر فاز در گرافهای تصادفی غیریکنواخت:

http://www.cs.cornell.edu/courses/cs4850/2010sp/Course%20Notes/Chapter%203%20Part%204%20Nonuniform%20degree%20models.pdf

من البته تغییر فاز برای ویژگی همبند بودن گراف را می‌خواستم. ولی حداقل فهمیدم کلاً چرا رفته بودیم سراغ این روش‌ها. آن روشی که می‌گوید همیشه یک تغییر فاز داریم فقط برای گرافهای اردوش-رینی برقرار است:

http://mathworld.wolfram.com/PhaseTransition.html

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

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