TUM – TUM – Menü

 

 
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.

Lectures will be given by Prof. Taraz and Prof. Noy, who has recently won an Alexander von Humboldt Research Award and is a visiting professor in our department.

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 Friday 16:00 02.08.011 Heinig April 27
Sheet 1 Wednesday 14:00 02.08.020 Heinig May 2
Sheet 2 Friday 16:00 02.08.011 Heinig May 11
Sheet 2 Wednesday 14:00 02.08.020 Heinig May 16
Sheet 3 Friday 16:00 02.08.011 Heinig May 25
Sheet 3 Wednesday 14:00 02.08.020 Heinig May 30
Sheet 4 Friday 16:00 02.08.011 Heinig June 8
Sheet 4 Wednesday 14:00 02.08.020 Heinig June 13
Sheet 5 Friday 16:00 02.08.011 Heinig June 22
Sheet 5 Wednesday 14:00 02.08.020 Heinig June 27
Sheet 6 Friday 16:00 02.08.011 Heinig July 6
Sheet 6 Wednesday 14:00 02.08.020 Heinig July 11
Last tutorial ( for questions concerning the course; there won't be anything new ) Friday 16:00 02.08.011 Heinig July 20

Solutions

File
Solutions to Sheet 1
Solutions to Sheet 2
Solutions to Sheet 3
Solution to a footnote in the Solutions to Sheet 3
Solutions to Sheet 4
Solutions to Sheet 5
Supplement to Sheet 5
Solutions to Sheet 6

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

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

question What role do the exercises play?
info 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.

question Do I have to register for the tutorials?
info 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.

question When and where will the exam take place?
info 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.

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

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

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

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

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

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

question What format does the resit exam have?
info 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).

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

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

Research Unit M9


Department of Mathematics
Boltzmannstraße 3
85748 Garching b. München
Germany
phone:+49 89 289-16858
fax:+49 089 289-16859
sekretariat-m9ma.tum.de

Professors

Prof. Dr. Peter Gritzmann
Applied Geometry and Discrete Mathematics

Prof. Dr. Andreas S. Schulz
Mathematics of Operations Research
(affiliated member of M9)

Prof. Dr. Stefan Weltge
Discrete Mathematics

News

April 2018
Case Studies 2018: Save the date: Case Studies poster presentation on May 25th, 2018, final workshop on July 7th, 2018.