Research

Research Interests

In particular, Enumerative and Probabilistic Combinatorics, Singularity Analysis, Probabilistic Methods, Planar Maps and Graphs, Random Graphs, Phase Transition, Random Sampling, Efficient Algorithms, Randomised Algorithms, Analysis of Algorithms

Research Stays

• New York University, Courant Institute of Mathematical Sciences, September - December 2009
• University of Oxford, Department of Statistics and Mathematical Institute, May - July 2009
• Charles University in Prague, Department of Applied Mathematics, March - April 2009
• Mittag-Leffler Institute, Research Program on Discrete Probability, February 2009
• Yonsei University, Department of Mathematics, March 2008
• École Polytechnique, Laboratoire d´Informatique, mid-September - mid-October 2007
• Centre de Recerca Matemática, Research Program on Enumerative Combinatorics and Random Structures, March 2007
• Adam Mickiewicz University, Faculity of Mathematics and Computer Science, October 2002 - March 2003

Organization of Workshops, Seminars and Schools

• MDS (Pre)Doc Course "Random and Quasirandom Graphs", 5 May - 27 June 2008
• Summer School "Extremal Graph Theory and Random Graphs", 31 July - 4 August 2006
• ASZ Learn and Workshops:
  
  • ASZ Workshop 2008, 20-21 June 2008
  • Random Graphs and Extremal Graph Theory, 6-7 July 2007
  • Random Graphs and Probabilistic Methods, 7-9 March 2005
  • Randomness, Geometry and Counting, 6-8 December 2004
• Annual Berlin-Poznan Seminar on Discrete Mathematics, since 2002

Professional Activities

• Junior faculty of Graduiertenkolleg: Methods for Discrete Structures
• Program Committee Member of Conferences:
  
  • The 21st International Symposium of Algorithms and Computation (ISAAC 2010), Jeju, Korea
  • Genetic and Evolutionary Computation Conference (GECCO 2009) - Formal Theory track, Montréal, Canada
  • The 3rd International Frontiers of Algorithmics Workshop (FAW 2009), Hefei, China
  • The 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009), New York, USA

Research Supervision

• Alexandros Droseltis, Master Thesis "Phase transition of a d-process on random graphs", 2008 (Co-supervisor: Prof. Dr. Uwe Küchler)
• Taral Guldahl Seierstad, Ph.D. Dissertation "The phase transition in random graphs and random graph processes", 2007 (Co-supervisor: Prof. Dr. Hans Jürgen Prömel)
• Stefan Vigerske, Master Thesis "Asymptotic enumeration of unlabeled outerplanar graphs", 2005
• Mike Löffler, Master Thesis "Counting and uniform generation of labeled planar structures", 2005
• Stefan Vigerske, Bachelor Thesis "Random outerplanar graphs", 2005 (Co-supervisor: Prof. Dr. Anusch Taraz)

Publications

Papers in Journals

• Quasi-randomness and algorithmic regularity for graphs with general degree distributions, accepted for publication in SIAM Journal on Computing, 23 pages (with Noga Alon, Amin Coja-Oghlan, Hiêp Hàn, Vojtěch Rödl and Mathias Schacht).
• The order of the giant component of random hypergraphs, accepted for publication in Random Structures and Algorithms, 28 pages (with Michael Behrisch and Amin Coja-Oghlan).
• Random preorders and alignments, accepted for publication in Discrete Mathematics, 24 pages (with Peter Cameron and Dudley Stark).
• The evolution of the min-min random graph process, Discrete Mathematics 309 (2009), 4527-4544 (with Amin Coja-Oghlan).
• The enumeration of planar graphs via Wick's theorem, Advances in Mathematics 221 (2009), 1703-1724 (with Martin Loebl).
• A complete grammar for decomposing a family of graphs into 3-connected components, Electronic Journal of Combinatorics 15 (2008), #R148, 39 pages (with Guillaume Chapuy, Éric Fusy and Bilyana Shoilekova).
• Generating unlabeled connected cubic planar graphs uniformly at random, Random Structures and Algorithms 34 (2008), 157-180 (with Manuel Bodirsky and Clemens Gröpl).
• The critical phase for random graphs with a given degree sequence, Combinatorics, Probability and Computing 17 (2008), 67-86 (with Taral Guldahl Seierstad).
• Enumeration and limit laws of series-parallel graphs, European Journal of Combinatorics 28 (2007), 2091-2105 (with Manuel Bodirsky, Omer Giménez and Marc Noy).
• Enumeration and asymptotic properties of unlabeled outerplanar graphs, Electronic Journal of Combinatorics 14 (2007), #R66, 24 pages (with Manuel Bodirsky, Éric Fusy and Stefan Vigerske).
• The phase transition of the minimum degree random multi-graph process, Random Structures and Algorithms 31 (2007), 330-353 (with Taral Guldahl Seierstad).
• Generating labeled planar graphs uniformly at random, Theoretical Computer Science 379 (2007), 377-386 (with Manuel Bodirsky and Clemens Gröpl).
• A direct decomposition of 3-connected planar graphs, Séminaire Lotharingien de Combinatoire 54A (2007), Article B54 Ak, 15 pages (with Manuel Bodirsky, Clemens Gröpl and Daniel Johannsen).
• Random cubic planar graphs, Random Structures and Algorithms 30 (2007), 78-94 (with Manuel Bodirsky, Mike Löffler and Colin McDiarmid).
• Generating outerplanar graphs uniformly at random, Combinatorics, Probability and Computing 15 (2006), 333-343 (with Manuel Bodirsky).
• The connectivity threshold for the min-degree random graph process, Random Structures and Algorithms 29 (2006), 105-120 (with Youngmee Koh, Tomasz Łuczak and Sangwook Ree).
• Maximum K_r+1-free graphs which are not r-partite, Mat. Studii 24 (2005), 12-20 (with Oleg Pikhurko).
• Random walks on finite graphs with congestion points, Applied Mathematics and Computation 153 (2004), 601-610.
• Efficiency test of pseudorandom number generators using random walks, Journal of Computational and Applied Mathematics 174 (2004), 165-177.
• First hitting times of simple random walks on graphs with congestion points, International Journal of Mathematics and Mathematical Sciences 30 (2003), 1911-1922.

Papers in Conference Proceedings

• Local Limit Theorems for the Giant Component of Random Hypergraphs. In the Proceedings of the 11th International Workshop on Randomization and Computation (RANDOM07), LNCS 4627, pages 341-352, 2007, Springer Verlag (with Michael Behrisch and Amin Coja-Oghlan).
• Quasi-randomness and algorithmic regularity for graphs with general degree distributions. In the Proceedings of the 34th International Colloquium on Automata, Languages and Programmnig (ICALP07), LNCS 4596, pages 789-800, 2007, Springer Verlag (with Noga Alon, Amin Coja-Oghlan, Hiêp Hàn, Vojtěch Rödl and Mathias Schacht).
• An unbiased pointing operator for unlabeled structures, with applications to counting and sampling. In the Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA07), pages 356-365 (with Manuel Bodirsky, Éric Fusy and Stefan Vigerske).
• Evolution of random graph processes with degree constraints. In the Proceedings of the Sixth Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications (2006). Electronic Notes in Discrete Mathematics 28 (2007), 493-500 .
• On the number of series-parallel and outerplanar graphs. In the Proceedings of European Conference on Combinatorics, Graph Theory and Applications (EuroComb05), DMTCS Proceedings Series, pages 383 - 388, 2005 (with Manuel Bodirsky, Omer Giménez and Marc Noy).
• Sampling unlabeled biconnected planar graphs. In the Proceedings of the 16th Annual International Symposium on Algorithms and Computation (ISAAC05), LNCS 3827, pages 593-603, 2005, Springer Verlag (with Manuel Bodirsky and Clemens Gröpl).
• Generating labeled planar graphs uniformly at random. In the Proceedings of the Thirtieth International Colloquium on Automata, Languages and Programming (ICALP03), LNCS 2719, pages 1095-1107, 2003, Springer Verlag (with Manuel Bodirsky and Clemens Gröpl).
• Decomposing, counting and generating unlabeled cubic planar graphs uniformly at random. In the Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EuroComb03), ITI Series 2003-145, pages 61-66, 2003 (with Manuel Bodirsky and Clemens Gröpl).

Preprints

• Random unlabelled graphs containing few disjoint cycles, submitted for publication in Random Structures and Algorithms (with Colin McDiarmid)
• Local limit theorems and number of connected hypergraphs, submitted for publication in Combinatorics, Probability and Computing (with Michael Behrisch and Amin Coja-Oghlan)
• Obfuscated drawings of planar graphs, submitted for publication in Discrete and computational Geometry (with Oleg Pikhurko, Alexander Ravsky, Mathias Schacht, and Oleg Verbitsky)
• On the logical complexity of dissections of a convex polygon, available at http://arxiv.org/abs/math.CO/0607531 (with Manuel Bodirsky and Oleg Verbitsky)
• Boltzmann samplers, Pólya theory and cycle pointing, in preparation (with Manuel Bodirsky, Éric Fusy and Stefan Vigerske)
• The two critical phase of a random planar graph, in preparation (with Tomasz Łuczak)

Translation

Korean version of The proofs from THE BOOK by Martin Aigner and Günter M. Ziegler, ISBN 9788981727246, Kyowoo Publishing Co.,Ltd, Seoul, 2008 (with Youngmee Koh and Sangwook Ree).

Teaching

At Humboldt-Universität zu Berlin

• Winter Semester 2007/08: Lecture - Probabilistic Method
• Summer Semester 2007: Lecture - Analytic Combinatorics
• Winter Semester 2006/07: Lecture - Randomized Algorithms and Probabilistic Analysis
• Summer Semester 2006: Lecture - Analytic Combinatorics and its Applications
• Winter Semester 2005/06: Lecture - Randomized Algorithms and Probabilistic Analysis
• Summer Semester 2005: Lecture - Combinatorics and its Applications
• Winter Semester 2004/05: Lecture - Randomized Algorithms and Probabilistic Analysis
• Summer Semester 2004: Lecture - Enumerative Combinatorics and Generating Functions
• Winter Semester 2003/04: Seminar - Discrete Random Walks: Theory and Applications
• Summer Semester 2003: Seminar - The strange Logic of Random Graphs