21-366: Introduction to Random Graphs, Fall 2020

Monday, Wednesday, Friday, 12:00pm, On-line:
Office hours: Tuesday, Thursday , 11:00am, on-line



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 three in-class tests.
               Homework: 25%
               Tests:          75%

Test dates: September 28.
                  November 9.
                  Last day of classes.

Tests: in class 50 minutes.

A:  >=80%

B:  >=70%

C:  >=60%


Homework.

Schedule.

Old Tests