21-366: Introduction to Random Graphs, Fall 2018

Monday, Wednesday, Friday 10.30, WEH6423:



We will follow the book
Introduction to Random Graphs: Hard Copy.
                                                     Digital Copy
Alan Frieze and Michal Karonski.


Old Notes, in addition to the book.


We study various models of a random graph i.e. a graph drawn from some probability distribution.
It is an interesting fact that in many cases we can predict with high probability (w.h.p.), what the values of
various parameters are.

For example, if G=G_n,m denotes a graph chosen uniformly at random from all graphs with vertex set [n]
and m edges, then if m=n^3/2log n, then w.h.p. G has diameter two.

We will discuss many such properties. We will endeavor to cover the following:

Chapter 1:   Random graph models.
Chapter 2:   Evolution of a random graph.
Chapter 3:   The degree sequence.
Chapter 4.   Connectivity.
Chapter 5.   Small sub-graphs.
Chapter 6.   Spanning sub-graphs.
Chapter 7.   Extreme characteristics.
Chapter 10. Fixed degree sequence.
Chapter 11. Intersection Graphs.
Chapter 12. Digraphs.
Chapter 17. Real world networks.
Chapter 18. Weighted graphs.

Grading: There will be weekly homeworks and four in-class tests.
               Homework: 10%
               Tests:          90%

I will calculate your grade from your eight best homeworks and your two best tests.

Test dates: September 21.
                  October 24.
                  December 7.

Homework.

Schedule.

Old Tests

Office hours: Tue, Fri, 4.00 - 5.00PM in WEH6204.