Graduate Seminar on Discrete Optimization (S4C1)
Summer 2020
Graph isomorphisms in quasipolynomial time
The talks in this seminar will be based mainly on the following papers:

Graph Isomorphism in Quasipolynomial Time, L. Babai, 2016

MonteCarlo algorithms in graph isomorphism testing, L. Babai, 1979

Finite Permutation Groups and Finite Simple Groups, P.J. Cameron, 1980, Bulletin of the London Mathematical
Society, 13, 122

An Examination of the Different Possible Solutions of a Problem in complete blocks, R.A. Fischer, 1940.

On the Combinatorial Power of the WeisfeilerLehman Algorithm, M. Fürer, 2017
 Algebraic Graph Theory, C. Godsil, G. Royle, 2001.

Graph Isomorphisms in QuasiPolynomial Time, H.A. Helfgott, 2017
(with an appendix by J. Bajpai and D. Dona)

Isomorphism of Graphs of Bounded Valence Can be Tested in Polynomial Time, E.M. Luks, 1981, Journal of Computer and System Sciences 25, 4265.

On tDesigns, D.K. RayChaudhuri, R.M. Wilson, 1975, Osaka Journal of Mathematics, 12, 737744.
There are two recommendable videos with László Babai
about his graph isomorphism
paper: see here
and here.
Due to the current situation, some changes in the organization are necessary:
 At least in the beginning, the talks will be held as zoom meetings

In order to test the technical setup and to discuss the organization of the
seminar, there will be a first zoom meeting on Monday, April 20, 14:15.
An invitation to the meeting will be sent to all participants.

On some days, we have two regular talks.
In this case, the first talk starts as usual at 14:15 while
the second talk starts at 15:30.

The approval talks follow the regular talks (see the schedule below).

The length of each talk should be between 50 and 60 minutes (plus 15 minutes for discussion).

We recommend to prepare slides for the presentation. A reasonable number of slides is between 30 and 40.
For further information, see also the the web pages of the
Bachelor Master Office Mathematics and of the
University of Bonn
This is a preliminary schedule. Talks and approval talks may be shifted by up to one week.
Number 
Approval Talk 
Talk 
Name 
Topic 
Mentoring 
1
 20.4. 14:45
 4.5. 14:15
 Felix Rosebrock
 MonteCarlo algorithms (paper(2))
 Benjamin Rockel

2
 27.4. 14:15
 11.5. 14:15
 Tobias Paszkiet
 The WeisfeilerLehman Algorithm (paper (5))
 Stefan Rabenstein

3
 4.5. 15:30
 18.5. 14:15
 Andreas Gwilt
 Section 2.1 of (7) and Sections 1 and 2 of (8)
 Pietro Saccardi

4
 4.5. 16:45
 18.5. 15:30
 Silas Rathke
 Section 2.2 of (7) and Sections 3 and 4 of (8)
 Anna Hermann

5
 11.5. 15:30
 25.5. 14:15
 Tin Sum Cheng
 Sections 2.3  2.5 of (7)
 Anna Hermann

6
 11.5. 16:45
 25.5. 15:30
 Daniel Blankenburg
 Sections 2.6  2.8 of (7) and (5) or (9)
 Anna Hermann

7
 18.5. 16:45
 8.6. 14:15
 Hanjo Thiele
 Section 3 of (7) and (3)
 Benjamin Klotz

8
 25.5. 16:45
 15.6. 14:15
 Annette Lutz
 Section 4 of (7) and Section 8 of (1)
 Tilmann Bihler

9
 8.6. 15:30
 22.6. 14:15
 Susanne Armbruster
 Section 5 of (7) I
 Tilmann Bihler

10
 8.6. 16:45
 22.6. 15:30
 Luise Puhlmann
 Section 5 of (7) II
 Tilmann Bihler

11
 15.6. 15:30
 29.6. 14:15
 Ekin Ergen
 Section 6 of (7)
 Benjamin Rockel

12
 22.6. 16:45
 6.7. 14:15
 Lars Friederichs
 Appendix A of (7)
 Benjamin Rockel


A regular participation in the talks and an active collaboration are mandatory for
passing the seminar.
 Each participant has to write a summary consisting of one or two pages.
 Each participant has to give an approval talk (typically two weeks
before the regular talk).
Passing the approval talk is a prerequisite for giving the regular seminar talk.
Prof. Dr. B. Korte,
Prof. Dr. J. Vygen,
Prof. Dr. S. Hougardy,
Prof. Dr. S. Held,
Dr. U. Brenner