Seminar Discrete Mathematics III

Winter 2014





In a nutshell...

Prerequisites: having a background in enumerative combinatorics and/or in the Probabilistic Method (roughly speaking, the material covered in DMII and DMIII in WS2013, SS2014)

Feel free to contact me at jrue at with any questions prior to the start of the course!

Requirements: the requirements of the seminar are here.

Syllabus: this seminar is a natural complement of the material studied in Discrete Mathematics II (WS 2013) and Discrete Mathematics III (SS 2014). The main objective is to cover, with more details some of the aspects that have appeared in both courses. In particular, we will focus our seminar in three different topics:

1.- Generating functions: the use of generating functions has been proved to be very successful in a wide variety of domains. We will explore their use in some applications in graph theory, permutations and walks in the plane. We will also see applications to random generation by means of the so-called Boltzmann samplers.

2.- Combinatorics of maps: embedded graphs (also called maps) play a central role in mathematics and not only in combinatorics. Nowadays, the study of these objects arise in different domains as statistical mechanics, algebraic geometry and probability, among others. We will cover some of the combinatorial results on this domain, including maps on surfaces, mobiles and blossoming trees, and the use of catalytic variables.

3.- The Probabilistic Method: the use of techniques arising from probability theory in discrete mathematics has been very fruitful for the last 60 years. And indeed, one cannot understand the development of combinatorics without paying attention to Probability Theory. We will explore some passages of this theory in discrete mathematics. We will focus ourselves in random graphs.

Schedule of the sessions





02/12/14 – 14:00

Josha Karsten

The symbolic Method can be applied in a very succesful way in order to study graph decompositions. We will show this principle in the context of planar graphs, as well as its connection with counting formulas for rooted planar maps.

Gimenez, Noy: Counting planar graphs and related families of graphs

Bodirsky, Kang, Löffler, Mcdiarmid: Random cubic planar graphs

02/12/14 – 16:00

Gregor Lagodzinski

We will exploit the disymmetry theorem for trees in order to deduce graph decompositions formulas which avoid integration steps. These methodology avoids technical problems which arise in enriched families of graphs.

Chapuy, Fusy, Kang, Shoilekova: A Complete Grammar for Decomposing a Family of Graphs into 3-connected Components

09/12/14 – 16:00

Sebastian Bierke

We study sets of matchings in complete bipartite graphs by using the so-called Lovasz Local Lemma. Applying this technique we study the existence of rainbow matchings and we count them.

Alon, Spencer: The probabilistic Method

Perarnau, Serra: Rainbow Matchings: Existence and Counting

16/12/14 – 14:00

Christoph Spiegel

A set of integers A is said to be Sidon if x,y,z,t in A satisfy that x+y=z+t, then {x,y}={z,t}. A natural problem is to construct dense infinite Sidon sequences.

In this seminar it will be showed how to get the best exponent known, namely sqrt(2)-1.

Ruzsa: An infinite Sidon sequence

Cilleruelo: Infinite Sidon sequences

13/01/15 – 14:00

Dimitris Bogiokas

The Erdös-Fuchs theorem in Combinatorial Number Theory states that the average behaviour of representation functions cannot be concentrated around a constant value.

In this talk we will show that error terms of order o(n^{1/4}) cannot hold, and that indeed this is the correct magnitude.

Newman: A simplified proof of Erdös and Fuchs
Ruzsa: A converse to a Theorem of Erdös and Fuchs

13/01/15 – 16:00

Florian Sadowski

The notion of planar map can be gengeneralized to compact surfaces without boundary. In this talk it will be shown how to extend Schaeffer's bijection in orientable surfaces.

Chapuy, Marcus, Schaeffer: A bijection for rooted maps on orientable surfaces

Chapuy: The structure of unicellular maps, and a connection between maps of positive genus and planar labelled trees

20/01/15 – 14:00

Julian Volland

The Stein method is a powerful tool in the context of the probabilistic method which provides normal limiting distributions in random discrete structures. We will present this method in the context of random graphs and some extensions

Barbour: Poisson convergence and random graphs

Rucinski: When are small subgraphs of a random graph normally distributed?

20/01/15 – 16:00

Julian Huth

Well Labelled positive Paths will be defined and some combinatorial properties will be defined. In particular, bijections with familes of matchings will be shown. Further consequences will be explained.

Bernardi, Duplantier, Nadeau: A bijection between well-labelled positive paths and matchings