Discrete Mathematics Masters' Seminar: (Advanced) Colouring and Counting

Summer 2015


Topics and References

Seminar Schedule

Grading and Requirements




Tibor Szabó Alexey Pokrovskiy Shagnik Das
Arnimallee 3, Rm 211a Arnimallee 3, Rm 207 Arnimallee 3, Rm 205
szabo at math dot fu-berlin dot de apokrovskiy at zedat dot fu-berlin dot de shagnnullik@mi.fu-bernulllin.de
Top of page

Topics and References

While (loosely) maintaining central themes of colouring and counting, this seminar will cover a wide variety of topics, providing a cross-section of active areas of research in combinatorics.

Below are a list of the talks that will be given, along with links to the source material.


Source material


The chromatic number of the Kneser graph Matoušek; Greene; Bárány; Lovász Tibor
The tightness of the Local Lemma Shearer Tibor
Bipartite Kneser graphs are Hamiltonian Mütze-Su Alexey
Counting and packing Hamilton cycles Ferber-Krivelevich-Sudakov Alexey/Tibor
Counting minimal separators Gaspers-Mackenzie Alexey
Ordered Ramsey numbers Conlon-Fox-Lee-Sudakov Alexey/Tibor
Ohba's conjecture on chromatic-choosable graphs Noel-Reed-Wu Shagnik/Tibor
Counting maximal intersecting families Nagy-Patkós Shagnik
Independent sets in regular graphs Kahn; Zhao Shagnik/Tibor
Top of page

Seminar Schedule

Our seminar will meet on selected Thursdays in Arnimallee 3, SR 210, from 2:15 pm to 5:45 pm. Each meeting will consist of two talks.

Below is the schedule for our seminar.





May 21 Alexander Jandt
Max Marcuse
The chromatic number of the Kneser graph T.B.A.
May 28 Giulia Codenotti
Teetje Stark
Ordered Ramsey numbers T.B.A.
June 4 Simon Treu The tightness of the Local Lemma T.B.A.
June 4 Darius Wuttke Bipartite Kneser graphs are Hamiltonian T.B.A.
June 11 Jennifer Friedrich
Svenja Horn
Counting and packing Hamilton cycles T.B.A.
June 18 Jan Corsten
Ricardo Euler
Independent sets in regular graphs T.B.A.
June 25 Tomas Bayer Counting maximal intersecting families T.B.A.
June 25 Björn Jeschke Counting minimal separators T.B.A.
July 2 Milan Möllenberg
Barbara Schulzke
Ohba's conjecture on chromatic-choosable graphs T.B.A.
Top of page

Grading and Requirements


If you have a partner for a double talk on a single topic, you should work together closely to understand your paper(s) and plan the individual talks.

Before the talks, you have to schedule at least two meetings with your adviser:
  • The first meeting should be at least two weeks before your scheduled talk. By this point, you should have read and worked through the paper(s) completely. The goal of this meeting is to clarify any parts of the material you do not fully understand. To this end, you should come prepared with concrete questions, such as, "How does line 45 follow from lines 23 and 38 in the proof of Theorem 3?" Simply saying, "I do not understand the proof of Theorem 3" is not acceptable.
  • The second meeting should be at least one week before your scheduled talk, and is practically a rehearsal. By this point, you should have your presentation completely prepared. If you are giving a Beamer presentation, all your slides should be completely finished - it is not okay to have any images or text missing. If you will be giving a blackboard presentation, you should have everything you plan to put on the board clearly written out, and notes on what you will be saying. The goal of this meeting is for the adviser to provide suggestions to improve the presentation ("This slide is too dense" or "Perhaps you should rearrange things here"). At this point you should also provide a short abstract for your talk(s) for the seminar website.
It is your responsibility to arrange the meeting with your adviser. Feel free to ask for additional meetings if you would like some additional input. If you miss or come unprepared to these meetings or your rehearsal fails to meet the minimum standards, your talk will be cancelled and you will not earn credit for the seminar.


You will be graded based on two criteria, both equally important:
  • your understanding of the topic, and
  • the quality of your presentation.
Failing either of these criteria will result in a failing grade for the seminar.

Attendance and activity

To earn credit for the seminar, you must attend 90% of the lectures and pepper your colleagues with questions demanding clearer explanations of anything you do not understand in their talks. The goal of the seminar is not to allow the speaker to repeat his or her rehearsed talk in a calm and quiet setting, but rather that we the audience learn and appreciate some nice new mathematics. Bear in mind that it is the speaker who is there to serve the audience, and not vice versa!
Top of page