Random Graphs
## Vorlesung / Lecture Course |

Lectures: | Marc Noy, Anusch Taraz |
---|---|

Exercises: | Peter Heinig |

Format: | 2+1 SWS |

ECTS-Credits: | 5 ECTS |

## News

- 8 october 2012: Grading of the exam of 5 october finished. You should be able to see your tentative grade via TUMonline now.
- 1 october 2012: Both for the exam on 5 october 2012 and the "Einsicht" on 10 october 2012, please remember to bring both your student id ("Studentenausweis") and your personal id. On Friday, please arrive on time.
- 12 august 2012: Exam grading is finished. If the software did what it said it did, you should now be able to see you tentative grade via the TUMonline system.
- The exam of 10 august 2012 with solutions will be on display for quite a while in one of the vitrines at the entrance of the M9 department.
- Both for the exam on 10 august and for the "Einsicht" on 14 august, please remember to bring both your student id ("Studentenausweis") and your personal id.
- 18 july: Solutions for Sheet 5 are online. A proof for the formula asked in Problem 5.1 is given in a supplementary sheet.
- 13 july: Solutions for Sheet 6 are online.
- 10 july: Notes for Lecture 10 are online.
- 8 july: Solutions for Sheet 5 will be delayed a bit longer, but will be made available as soon as possible.
- 5 july: the formulation of Lemma 3.6 on the blackboard in Lecture 10 from 27 june 2012 was a bit too general. Please replace it with the formulation in Problem 6.2. Moreover, Lecture 10 will soon be available from this webpage.
- 4 july: Sheet 6 is online. Solutions for Sheet 5 stand a good chance of being online by the end of this week.
- 26 june: Time and place for exam are now confirmed. See FAQ.
- 19 june: Sheet 5 is online. Solutions for Sheet 4 are online.
- 10 june: solutions for Sheet 3 are online.
- 5 june: Sheet 4 is online. Solutions for Sheet 3 have a good chance of being available this week.
- 21 may: solutions for Sheet 2 are online. Sheet 3 is online.
- 11 may: In the tutorial it was asked what `outdegree' means in Problem 2.5. Saying `every vertex has even outdegree' is just another way of saying `every vertex of the tree has an even number of children'. There are examples for this usage in the book of Flajolet and Sedgewick. Moreover, for higher explicitness you can replace `ternary trees' with `plane ternary trees' in Problem 2.5. For `k-ary tree', the default meaning tends to be `plane k-ary tree' and this convention was used in the lecture of 9 may 2012.
- 8 may: solutions for Sheet 1 are online. Sheet 2 is online.
- Since the Fachschaftsvollversammlungen end at 12.00, the tutorial on 2 may 2012 will take place as scheduled.
- 24 april: Sheet 1 is available. Since this was asked in the tutorial: In Problem 1.1 the property "k-connected" means "k-vertex-connected" in the standard graph-theoretical sense, i.e. "for every (k-1)-element subset S of the vertex set, deleting S and all incident edges from G still leaves a connected graph". Hint for Problem 1.4.(4): This can be done with tools from Lecture 2. The earlier parts of Problem 1.4 could help you set up a formalism sufficient to prove the statement.
- 20 april: Sheet 1 is not finished yet. It will be available by 25 april.
- First lecture on april 18. We highly recommend the talks by Prof. Noy and Prof. Steger in our Colloquium on the same day:

see http://www.ma.tum.de/Mathematik/FakultaetsKolloquium

## Contents of the course

Random graphs were first considered as a mere tool for proving the existence of graphs with particular properties, but they now form a field of study in their own right. In many cases, they provide appropriate models for real-world networks, and the investigation of their typical properties can build foundations for the average-case analysis of algorithms in optimization.In this course we will deal with

- the binomial model G(n,p)
- its phase transition(s)
- constrained random graphs: random trees, random regular graphs
- randomized algorithms and average-case analysis
- probabilistic methods: first and second moments, large deviation inequalities, generating functions, Markov chains.

## Target audience

The course is aimed at Master students who would like to complement the lectures on optimization. Bachelor students are of course also invited to attend.## Prerequisites for the course

- Background in Discrete Mathematics, Analysis, Linear Algebra, Probability

# Dates

## Dates of lectures / exercise classes

Type | Day | Time | Room | Teacher | Dates |
---|---|---|---|---|---|

Lecture | Wednesday | 10:15 Uhr | MI HS 3 | Noy / Taraz | every week, starting April 18 |

Sheet 1 | Wednesday | 14:00 | 02.08.020 | Heinig | May 2 |

Sheet 2 | Wednesday | 14:00 | 02.08.020 | Heinig | May 16 |

Sheet 3 | Wednesday | 14:00 | 02.08.020 | Heinig | May 30 |

Sheet 4 | Wednesday | 14:00 | 02.08.020 | Heinig | June 13 |

Sheet 5 | Wednesday | 14:00 | 02.08.020 | Heinig | June 27 |

Sheet 6 | Wednesday | 14:00 | 02.08.020 | Heinig | July 11 |

Sheet 1 | Friday | 16:00 | 02.08.011 | Heinig | April 27 |

Sheet 2 | Friday | 16:00 | 02.08.011 | Heinig | May 11 |

Sheet 3 | Friday | 16:00 | 02.08.011 | Heinig | May 25 |

Sheet 4 | Friday | 16:00 | 02.08.011 | Heinig | June 8 |

Sheet 5 | Friday | 16:00 | 02.08.011 | Heinig | June 22 |

Sheet 6 | Friday | 16:00 | 02.08.011 | Heinig | July 6 |

Last tutorial ( for questions concerning the course; there won't be anything new ) | Friday | 16:00 | 02.08.011 | Heinig | July 20 |

## Solutions

## Lecture notes

Day | File | Topics |
---|---|---|

18.04.2012 | Lecture 1 | 1. Introduction |

25.04.2012 | Lecture 2 | 1. Introduction: 1.6 Tools from Probability Theory |

09.05.2012 | Material on combinatorial enumeration | Chapter 2 |

20.06.2012 | Lecture 9 | 3. Evolution of random graphs |

27.06.2012 | Lecture 10 | 3. Evolution of random graphs |

04.07.2012 | Lecture 11 | 3. Evolution of random graphs, 4. Clique and Chromatic number of random graphs |

11.07.2012 | Lecture 12 | 4. Clique and Chromatic number of random graphs |

18.07.2012 | Lecture 13 | 4. Clique and Chromatic number of random graphs |

## Literature

- S. Janson, T. Łuczak, A. Ruciński: Random Graphs. Wiley.
- B. Bollobás: Random Graphs. Cambridge University Press.
- N. Alon, J. Spencer: The Probabilistic Method. Wiley.
- P. Flajolet, R. Sedgewick: Analytic Combinatorics.
^{}Cambridge University Press. - R. Motwani, P. Raghavan: Randomized Algorithms. Cambridge University Press.

## FAQ

*How will the grade for the course be determined?*The grade for the course will be 100% determined by the final exam.

*What role do the exercises play?*The exercises are an offer to prepare yourself for the final exam. While with a view toward the exam you are strongly encouraged to do all the exercises in written form, there will be no credits for written solutions.

*Do I have to register for the tutorials?*Since the the exercise system does not comprise a grade bonus, there will not be a registration via TUMonline for the tutorials. You are free to go to those that suit you.

*When and where will the exam take place?*Friday, 10 august 2012, 10.00 am, in 5503.EG.350 (MW 0350, Egbert-von-Hoyer-Hörsaal). Map. This room is easy to find: if you enter the building of the Maschinenwesen from the east, just go straight along the hallway on the ground floor while keeping an eye on the lecture halls to your left. One of them sports the name "Egbert-von-Hoyer" in white letters on a grey background.

*Which auxiliary material am I allowed to use during the exam?*None, except for writing utensils.

*How long does the exam last?*The exam lasts 60 minutes.

*When and where can I see my graded exam ("Einsicht")?*Tuesday, 14 august 2012, 10.00 -- 11.00 am, in room 02.04.011.

*Where can I get solutions for the exam of 10 august 2012?*In one of the vitrines at the entrance of the M9 department.

*Am I automatically registered for the resit exam if I have failed the exam of 10 august 2012?*No. You have to register again via TUMonline. Registration is now possible (until 17 september 2012).

*When and where will the resit exam take place?*In 00.06.011 (MI Hörsaal 3) on 5 october 2012 from 14.00 -- 15.00 pm.

*What format does the resit exam have?*Exactly the same as the exam on 10 august 2012. Again, the examinable material are all lectures and all exercise sheets as they appeared in late July (in particular, no improvements to the exercise sheets will be made until after the resit exam).

*When and where can I see my graded exam ("Einsicht")?*Wednesday, 10 october 2012, 14.00 -- 15.00 pm, in room 02.06.020.

*Where can I get solutions for the exam of 5 october 2012?*In one of the vitrines at the entrance of the M9 department.