Random Structures and Real World Graphs

1st semester - 2019

lunedì 16:00, giovedì 9:00

aula F3

Contents

basic probability, random variables, deviation bounds
random graphs models and properties
real world graphs

Texts

class notes
Probability and Computing, Mitzenmacher and Upfal (MU)
Networks, Crowds, and Markets, Kleinberg and Easley (KE) (download)

Evaluation

The final grade will be composed by:

40% from the exercises
60% from the 2 exams (30%+30%)

The exams:

Exam #1:
- October 17h
- based on the first six classes (from "Introduction and Axioms" to "Complete Subgraphs and MAX-CUT")
Exam #2:
- November 14h
- based on the seventh class until the last class

The exercises:

The exercises refer to the 1st Edition of the MU book
The exercises must be delivered within 7 days after the class

Class Notes

ADVICE: Bring previously printed class notes to the class

NOTES	SLIDES	EXERCISES	BOOK REFERENCE
Introduction and Axioms	(slides)	(exercises)	MU - 1.1 and 1.2
Basic Probability Results	(slides)	(exercises)	MU - 1.2 and 1.3
Minimum Global Cut		(exercises)	MU - 1.4
Random Variables and Expectation		(exercises)	MU - 2.1
Random Graphs		(exercises)	MU - 5.6
Complete Subgraphs and MAX-CUT	(slides)	(exercises)	MU - 6.1 and 6.2
Large Independent Sets and Girths		(exercises)	MU - 6.4
Markov's Inequality and Variance		(exercises)	MU - 3.1 and 3.2
Chebyshev's Inequality and Applications		(exercises)	MU - 3.3
Chernoff Bounds and Properties of Random Graphs		(exercises)	MU - 4.2 and 5.6.1 (2nd ed. only)
Complex Networks		(exercises)	KE - 2 and 20
Inhomogeneous Random Graph Models	(slides)	(exercises)
Power Law (Degree) Distribution		(exercises)	KE - 18 and MU - 16 (2nd ed. only)

Office hours

after class or schedule by email