|
Seminar Discrete Mathematics IIIWinter 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 zedat.fu-berlin.de 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
When? |
Who? |
What? |
References |
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. |
|
|
|
|
|
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. |
|
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. |
|
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 |
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 |
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 |