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=Gn,m denotes a graph chosen
uniformly at random from all graphs with vertex set [n]
and m edges, then if m=n3/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