ALEA in Europe Young Researcher's Workshop

Vienna, Austria
September 6-9, 2016


Course 1 - Cécile Mailler

Probability: Reinforced Branching Processes

The aim of this course is to define the notion of reinforced branching processes and give tools to study them, starting with a crash course on continuous-time martingales.

Although reinforced branching processes are interesting objects in themselves, I chose to motivate their definition by looking at one particular case: the preferential attachment tree with fitnesses introduced by Bianconi and Barabási as a model for complex networks. This model is a discrete-time random process on the set of rooted trees, but if we embed this process in continuous time with the help of random exponential clocks, we obtain a continuous-time process called a reinforced branching process.

Reinforced branching processes can be seen as population processes with immortal particles. They are a particular case of the more general Crump-Mode-Jägers processes for which tools are available, especially when they admit a Malthusian parameter. We will show how to apply these methods, but will then focus on the case when there is no Malthusian parameter.

In this latter case, a phenomenon called condensation occurs: in terms of networks, it means that there exists a small set of nodes (typically sublinear in the size of the network) such that the sum of the degrees of these nodes is linear in the size of the network. If there exists one node having linear degree in terms of the size of the network, we say that the winner takes it all or that there is extensive condensation.

Our aim is to understand under what condition there is condensation, and whether this is extensive or non-extensive condensation. We will briefly introduce the main tools to study reinforced branching processes: martingales, Crump-Mode-Jägers processes, random point processes.

Lecture notes - Solution of the exercises

Course 2 - Élie de Panafieu

Analytic Combinatorics: Random Graphs

Analytic combinatorics is useful for the enumeration of graph families, and the derivation of properties large graphs typically satisfy. We first present classic results on the most common model, G(n,m), concerning connected graphs and the structure of random graphs. Then variants of the G(n,m) model are introduced, with constraints on the degrees of the vertices, the number of vertices allowed in each edge (hypergraphs), or with colored vertices which connectivity varies according to their color (inhomogeneous graphs). This presentation focuses on the combinatorial decompositions and the generating function manipulations, avoiding all analytic technicalities.

Lecture notes

Course 3 - Rika Yatchak

Computer Algebra: Gröbner Bases for Combinatorics

This course is intended as an invitation to computer algebra. We will begin with a crash course in Gröbner basis theory, including classical applications such as implicitization and elimination. We will continue by investigating how Gröbner bases can be useful in various concrete combinatorial applications such as colorings of graphs, the Frobenius coin problem, restricted lattice walks, and polytopes. We will close by discussing Gröbner basis for operators. A computer algebra system such as Sage or Mathematica is not required for the course, but will aid in the computation of examples and some of the exercises.