VVZ API is not affiliated with ETH Zurich. Data might be outdated or incorrect. Please view the official ETHZ Vorlesungsverzeichnis for binding information.
Abstract
This lecture deals with the basic techniques and results in random graph theory. The following topics are introduced: First- and second moment method, concentration inequalities, thresholds, two-round exposure, isolated vertices, clique number, chromatic number, hamiltoncycles, giant component, regular graphs (pairing model).
Objective
Ziel dieser Vorlesung ist es, den Hörer in die Theorie der zufälligen Graphen einzuführen und mit den grundlegenden Phänomenen und Techniken vertraut zu machen. Behandelt werden insbesondere die folgenden Themen: First and second moment Methode, 0-1 Gesetzte (Schwellenwerte), maximale Clique, chromatische Zahl, Hamiltonkreise, grösste Zusammenhangskomponente.
Resources
Lecture Notes
Lecture notes will be distributed.
Literature
- Bela Bollobas: Random Graphs, CUP, 2001 (2nd Ed.) - Janson, Luczak, Rucinski: Random Graphs, J. Wiley and Sons, 2000
General Information
- Language
- German
- Levels
- BSC , DS
- Frequency
- Every two years
Examination
- Type
- end-of-semester examination
Course Components
| Type | Title | Time & Place | Hours |
|---|---|---|---|
| lecture |
Zufällige Graphen
Does not take place this semester.
|
No time listed | 2 h weekly |
| exercise |
Zufällige Graphen
Does not take place this semester.
|
No time listed | 1 h weekly |