Random Structures and Real World Graphs

1st semester - 2019

lunedì 16:00, giovedì 9:00

aula F3


Contents

  1. basic probability, random variables, deviation bounds
  2. random graphs models and properties
  3. real world graphs

Texts

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

Evaluation

The final grade will be composed by:

The exams: The exercises:

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