Vienna, Austria
October 9-13, 2017

Program

Abstracts

Christian Krattenthaler

Lattice paths and (bi)orthogonal polynomials

It is well-known (at least in principle...) that the enumeration of Motzkin-type paths is intimately related to the theory of orthogonal polynomials, via Xavier Viennot's corresponding combinatorial theory. It is perhaps less well-known (at least, this was the case for me until recently) that the enumeration of Schr\"oder-like paths is intimately related to the theory of biorthogonal polynomials, via a recent combinatorial theory developed by Shuhei Kamioka. My plan is to start with a review of Viennot's combinatorial theory of orthogonal polynomials and then present Kamioka's combinatorial theory of biorthogonal polynomials.

Conrado Martinez

Data Stream Analysis: a (new) triumph for Analytic Combinatorics

Slides Exercises

Ralph Neininger

Stochastic fixed-points and periodicities in combinatorial structures

Slides Exercises

Long talks (50 min.)

Pierre Calka

The Poisson-Voronoi cell around an isolated nucleus

Geometric probability is the study of geometric figures, in general from the Euclidean space, which have been randomly generated. In this talk, we concentrate on the two-dimensional Poisson-Voronoi tessellation, which is a classical model of random partition of the plane into convex polygons called cells and which is generated by a random set of points called nuclei. We fix a convex body K and we condition the tessellation on the event that K is included in one cell. We then obtain the asymptotic means of the characteristics of this particular cell. We also solve a dual problem when the set of nuclei has a large hole. This is joint work with Yann Demichel (Université Paris Nanterre) and Nathanaël Enriquez (Université Paris-Sud).

Slides

Bernhard Gittenberger

Enumeration of Compacted Trees with Height Restrictions

When storing a rooted tree, it is better not to store isomorphic subtrees separatly, but only once and to represent the others by pointers. A classical algorithm to establish such a compaction was analyzed by Flajolet and Steyaert. The resulting structure is called compacted tree, being in fact no more a tree but a directed acyclic graph instead.

Our goal is the enumeration of such structures. Since the enumeration turns out to be extremely hard, we simplify the problem by imposing a bound on the so-called right-height. This leads to an interesting enumeration problem, for which we need to develop a calculus for exponential generating function for this unlabelled structure. Eventually, this leads to a sequence of differential equation for the generating functions for which a singularity analysis has to be carried out. Approaching the problem first by a further simplification, we solve the asymptotic counting problem for both the simple and the less simple structures after all.

Based on joint work with Antoine Genitrini, Manuel Kauers, and Michael Wallner.

Hsien-Kuei Hwang

Probabilistic analysis of (1+1)-Evolutionary Algorithm

I will present a probabilistic analysis of the optimization time of the (1+1)-Evolutionary Algorithm under two simple fitness functions (ONEMAX and LEADINGONES). The problem has been approached in the evolutionary algorithm literature in various ways and with different degrees of rigor. The asymptotic approximations I will present for the mean and the variance represent the strongest of their kind. The approach used is based on an asymptotic resolution of the underlying recurrences and can also be extended to characterize the corresponding limiting distributions. While most of our approximations can be derived by simple heuristic calculations based on the idea of matched asymptotics, the rigorous justifications are challenging and require a delicate error analysis. (This talk is based on joint work with Alois Panholzer, Nicolas Rolin, Tsung-Hsi Tsai and Wei-Mei Chen.)

Slides

Christoph Koutschan

Symbolic evaluation of determinants and rhombus tilings of holey hexagons

We consider the problem of evaluating (or proving, if known) the determinant of a matrix whose dimension is a symbolic parameter. The "holonomic ansatz", that was proposed by Doron Zeilberger in 2007, makes this problem accessible to computer algebra methods. As an application, we investigate a curious determinant that was first mentioned by George Andrews in 1980 in the context of descending plane partitions. It is found to be a special instance of some family of determinants that count cyclically symmetric rhombus tilings of a hexagon with several triangular holes inside.

Slides

Cécile Mailler

Multi-drawing multi-colour urns

A classical Pólya urn scheme is a Markov process whose evolution is encoded by a replacement matrix $(R_i,j)_(1≤i,j≤d)$ . At every discrete time-step, we draw a ball uniformly at random, denote its colour c, and replace it in the urn together with R_c,j balls of colour j (for all 1 ≤ j ≤ d).

This talk will focus on multi-drawing Pólya urns, where the replacement rule depends on the random drawing of a set of m balls from the urn (with or without replacement). I will show how to apply stochastic approximation methods to get up-to-second-order limit theorems for balanced (but not “affine” urn schemes). This is a joint work with Nabil Lasmar and Olfa Selmi (Monastir, Tunisia).

Slides

Irène Marcovici

Probabilistic cellular automata with memory two

A central question on probabilistic cellular automata (PCA) is to study equilibrium behaviours. An equilibrium is characterized by an invariant measure, that is, a probability distribution on the configuration space, which is left invariant by the dynamics. When the invariant measure is unique and attractive, the PCA is said to be ergodic, meaning that during its evolution, it eventually forgets about its initial condition. Assessing the ergodicity of a PCA is algorithmically undecidable, even for the simplest class of PCA. Furthermore, apart from some specific cases, we have generally no explicit description of the invariant measures of PCA.

I will present some new results concerning PCA with memory two, that were motivated by the study of models coming from statistical physics (8-vertex model, TASEP...). We characterize PCA with memory two having an invariant measure with a product form or a Markovian form, and by exploring a family of PCA presenting a phenomenon of multi-directional reversibility, we also exhibit some other cases where the invariant measure is exactly computable. This is a joint work with Jérôme Casse.

Slides

Henning Sulzbach

Asymptotic expansions for the profile of random trees

Binary search trees and their variants are of prime importance in computer science allowing for efficient execution of database operations such as insertion, deletion and retrieving of data. Their properties have been analysed over the last thirty years (and longer) by various techniques of analytic, combinatorial and probabilistic kind. In this talk, I discuss the so-called tree profile counting the number of nodes of a given depth encompassing many important quantities such as the height and the fill-up level. In this context, I will present a family of novel strong functional limit theorems settling several open problems raised in Devroye and Hwang [2006], Fuchs, Hwang and Neininger [2006], and Drmota and Hwang [2005] on the width of the tree (i.e. the maximal number of nodes on any level) and the mode of the profile (i.e. the level where the width is attained). I discuss two kinds of extensions: first, the techniques apply to related tree models such as random recursive trees and linear increasing trees. Second, the methodology covers more complex situations when nodes are distinguished by their out-degrees or subtree structures. All results follow from more general expansions for (stopped) continuous-time (multi-type) branching random walks. The talk is based on joint work with Zakhar Kabluchko and Alexander Marynych (Muenster).

Slides

Short talks (25 min.)

Axel Bacher

Limit laws of anticipated rejection and related algorithms

I will present several random generation algorithms based on the concept of anticipated rejection (foremost among them are the Florentine algorithms, by Barcucci et al.). I will show how, in some cases, these algorithms may be improved by dispensing with the rejection altogether. Finally, I will study the unusual limit laws that occur in the analysis of these algorithms.

Slides

Cyril Banderier

D-finiteness and generalized Mittag-Leffler distributions

We introduce a model of urns with periodic behaviour. We show that this leads to a solvable model in terms of generalized hypergeometric functions and other D-finite functions. The limit law for the asymptotic composition of the urn lies in the realm of generalized gamma functions, generalized Mittag-Leffler distributions. This work allows to analyze the limiting behaviour of the lower right cell of a Young Tableau (see the talk by Philippe).

Joint work with Philippe Marchal and Michael Wallner.

Michael Borinsky

Generating asymptotics for factorially divergent sequences

In general, formal power series may have a vanishing radius of convergence. In this case, singularity analysis becomes inapplicable to obtain the asymptotics of the coefficients. However, if we restrict ourselves to the subspace of power series which grow at most factorially, rich algebraic structures can be found, which allow the extraction of asymptotics in a different way. The subspace of these power series is closed under multiplication, composition and inversion of power series. An operator can be defined, which maps a power series to its own asymptotic expansion. This operator turns out to be a derivation which fulfills product and chain rules. These rules allow the very efficient extraction of asymptotic expansions of implicitly defined power series with factorial growth. I will present these techniques, which are based on the work of Edward Bender, and give the complete asymptotic expansions of simple permutations and connected chord diagrams as examples.

Slides

Mihyun Kang

Homological connectivity of random hypergraphs

We consider 2-dimensional simplicial complexes that are generated from the binomial random 3-uniform hypergraph by taking the downward-closure. We determine when this simplicial complex is homologically connected, meaning that its zero-th and first homology groups with coefficients in F_2 vanish. Although this is not intrinsically a monotone property, we show that it nevertheless has a single sharp threshold, and indeed prove a hitting time result relating the connectedness to the disappearance of the last minimal obstruction. (Joint work with Oliver Cooley, Penny Haxell, and Philipp Sprüssel.)

Andrea Kuntschik

Rates of convergence for balanced, irreducible Pólya urns with two colours

For the class of balanced, irreducible Pólya urn schemes with two colours, say black and white, limit theorems for the number of black balls after n steps are known. Depending on the ratio of the eigenvalues of the replacement matrix, two regimes of limit laws occur: almost sure convergence to a non-degenerate random variable whose distribution depends on the initial composition of the urn and that is known to be not normally distributed and weak convergence to the normal distribution. We give upper bounds on the rates of convergence in both the non-normal limit case and the normal limit case. Parts of the results confirm a conjecture of Svante Janson.

Philippe Marchal

The law of the corner of a Young tableau

Fix a Young diagram and consider a random standard filling. What is the distribution of the entry in the southeast corner (using the French convention) ? We show that this question can be answered using a link with a problem on trees. In particular, when the diagram is triangular, this amounts to an unusual model of urns with periodic conditions.

Slides