AofA 2014

25th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms

Paris, France, June 16–20, 2014


Program

The conference will be held in Jussieu, in the premises of Université Pierre et Marie Curie. It will last five days, from June 16 to 20, 2014.

Abstracts of talks are available in the program below (just pass your mouse on the title to see the abstract). You can also download the pdf file of all abstracts here.

A compact view of the program as a one-page pdf file is available here.

group photo preview Click here for the GROUP PHOTO!

Monday, June 16

08:30–09:00 Welcome
09:00–10:00 Donald Knuth
Problems Philippe Would Have Liked (Flajolet Lecture) (slides)
The speaker will discuss several intriguing problems that he believes are unsolved, and for which solutions may well open up new techniques of general importance for the analysis of algorithms. He cannot help but remember a lecture that David Hilbert once gave in Paris, although he warns the audience not to expect problems of Hilbertian quality.
10:00–10:30 Coffee Break
10:30–11:00 Axel Bacher and Andrea Sportiello
Anticipated rejection algorithms and the Darling-Mandelbrot distribution. (slides)
We study in limit law the complexity of some anticipated rejection random sampling algorithms. We express this complexity in terms of a probabilistic process, the threshold sum process. We show that, under the right conditions, the complexity is linear and admits as a limit law a so-called Darling--Mandelbrot distribution, studied by Darling (1952) and Lew (1994). We also give an explicit form to the density of the Darling--Mandelbrot distribution and derive some of its analytic properties.
11:00–11:30 James Zhao
A Linear-Time Algorithm for Sampling Graphs with Given Degrees. (slides)
We introduce a new algorithm for the asymptotically uniform sampling of graphs with given degrees, combining elements of combinatorial and Markov Chain Monte Carlo methods into a hybrid strategy. Under a typical sparseness condition, the runtime is linear in the number of edges, improving upon the previous best runtime by a factor equal to the maximum degree. We go on to show that this idea is applicable to a variety of other combinatorial families.
11:30–12:00 Markus E Nebel and Sebastian Wild.
Pivot Sampling in Dual-Pivot Quicksort – Exploiting Asymmetries in Yaroslavskiy’s Partitioning Scheme (slides)
The new dual-pivot Quicksort by Vladimir Yaroslavskiy, used in Oracle's Java runtime library since version 7, features intriguing asymmetries in its behavior. They were shown to cause a basic variant of this algorithm to use less comparisons than classic single-pivot Quicksort implementations. In this paper, we extend the analysis to the case where the two pivots are chosen as fixed order statistics of a random sample and give the precise leading term of the average number of comparisons, swaps and executed Java Bytecode instructions. It turns out that, unlike for classic Quicksort, where it is optimal to choose the pivot as median of the sample, the asymmetries in Yaroslavskiy's algorithm render pivots with a systematic skew more efficient than the symmetric choice. Moreover, the optimal skew heavily depends on the employed cost measure; most strikingly, abstract costs like the number of swaps and comparisons yield a very different result than counting Java Bytecode instructions, which can be assumed most closely related to actual running time.
12:00–14:00 Lunch
14:00–14:30 Svante Janson and Alfredo Viola
A unified approach to linear probing hashing. (slides)
We give a unified analysis of linear probing hashing with a general bucket size. We use both a combinatorial approach, giving exact formulas for generating functions, and a probabilistic approach, giving simple derivations of asymptotic results. Both approaches complement nicely, and give a good insight in the relation between linear probing and random walks. A key methodological contribution, at the core of Analytic Combinatorics, is the use of the symbolic method (based on $q$-calculus) to directly derive the generating functions to analyze.
14:30–15:00 Nicolas Broutin, Olivier Devillers and Ross Hemsley
Efficiently Navigating a Random Delaunay Triangulation. (slides)
Planar graph navigation is an important problem with significant implications to both point location in geometric data structures and routing in networks. Whilst many algorithms have been proposed, very little theoretical analysis is available for the properties of the paths generated or the computational resources required to generate them. In this work, we propose and analyse a new planar navigation algorithm for the Delaunay triangulation. We then demonstrate a number of strong theoretical guarantees for the algorithm when it is applied to a random set of points in a convex region.
15:00–15:30 Coffee Break
15:30–16:00 Vincent Pilaud and Juanjo Rué
Analytic combinatorics of chord and hyperchord diagrams with k crossings. (slides)
Using methods from Analytic Combinatorics, we study the families of perfect matchings, partitions, chord diagrams, and hyperchord diagrams on a disk with a prescribed number of crossings. For each family, we express the generating function of the configurations with exactly $k$ crossings as a rational function of the generating function of crossing-free configurations. Using these expressions, we study the singular behavior of these generating functions and derive asymptotic results on the counting sequences of the configurations with precisely $k$ crossings. Limiting distributions and random generators are also studied.
16:00–16:30 Antoine Genitrini, Bernhard Gittenberger and Cécile Mailler
No Shannon effect induced by And/Or trees. (slides)
Quantitative logic has been the subject of an increasing interest since a seminal paper by Chauvin et al. in 2004, which presented the first Analytic Combinatorics approach of the subject. Since then, the understanding of random Boolean trees has been deeply widened, even if the question of Shannon effect remains open for the majority of the models. We focus in this paper on the original case of Catalan \texttt{And/Or} trees and propose a new specification of those objects that implies easier ways to describe large families of trees. Equipped with this specification, we prove that the model of Catalan \texttt{And/Or} binary trees do not exhibit Shannon effect, i.e. there exists a family of functions with small complexities, that have a positive probability.
16:30–18:00 Poster Session (see here)
18:00– Cocktail

Tuesday, June 17

09:00–10:00 Colin McDiarmid
Random graphs from a minor-closed class (Invited Talk) (slides)
Consider a minor-closed class of graphs, such as the class of planar graphs. What can we say in general about typical graphs in the class? Can we learn things that could be useful for the design or analysis of algorithms?
10:00–10:30 Coffee Break
10:30–11:00 Mihyun Kang, Angelica Pachon and Pablo Rodriguez
Connectivity for a modified binomial random graph by agglomeration.
In the classical Erd\H os-R\'enyi random graph $G(n,p)$ there are $n$ vertices and each of the possible edges is independently present with probability $p$. One of the most known results for this model is the threshold for connectedness, a phenomenon which is tightly related to the nonexistence of isolated vertices. Numerous random graphs inspired in real networks are inhomogeneous in the sense that not all vertices have the same characteristic, which may influence the connection probability between pairs of vertices. The random graph $G(n,p)$ is homogeneous in this respect. Thus, with the aim to study real networks, new random graph models have been introduced and analyzed recently. The purpose of this paper is to contribute to this task by proposing a new inhomogeneous random graph model which is obtained in a constructive way from the classical Erd\H os-R\'enyi model. We consider an initial configuration of subsets of vertices and we call each subset a super-vertex, then the random graph model is defined by letting two super-vertices be connected if there is at least one edge between them in $G(n,p)$. Our main result concerns the threshold for connectedness. We point out that even though our model begins from $G(n,p)$, it assumes the existence of community structure and under certain conditions it exhibits a power law degree distribution, both important properties for real applications.
11:00–11:30 Abram Magner, Svante Janson, Giorgos Kollias and Wojciech Szpankowski
On Symmetry of Uniform and Preferential Attachment Graphs. (slides)
Motivated by the problem of graph structure compression under realistic source models, we study the symmetry behavior of preferential and uniform attachment graphs. These are two dynamic models of network growth in which new nodes attach to a constant number $m$ of existing ones according to some attachment scheme. We prove symmetry results for $m=1$ and $2$, and we conjecture that for $m\geq 3$, both models yield asymmetry with high probability. We provide new empirical evidence in terms of graph defect. We also prove that vertex defects in the uniform attachment model grow at most logarithmically with graph size, then use this to prove a weak asymmetry result for all values of $m$ in the uniform attachment model. Finally, we introduce a natural variation of the two models that incorporates preference of new nodes for nodes of a similar age, and we show that the change introduces symmetry for all values of $m$.
11:30–12:00 Pascal Maillard and Elliot Paquette
Choices and Intervals. (slides)
We consider a random interval splitting process, in which the splitting rule depends on the empirical distribution of interval lengths. We show that this empirical distribution converges to a limit almost surely as the number of intervals goes to infinity. We give a characterization of this limit as a solution of an ODE and use this to derive precise tail estimates. The convergence is established by showing that the size-biased empirical distribution evolves in the limit according to a certain deterministic evolution equation. Although this equation involves a non-local, non-linear operator, it can be studied thanks to a carefully chosen norm with respect to which this operator is contractive. In finite-dimensional settings, convergence results like this usually go under the name of \emph{stochastic approximation} and can be approached by a general method of Kushner and Clark. An important technical contribution of our work is the extension of this method to an infinite-dimensional setting.
12:00–14:00 Lunch
14:00–14:30 Katarzyna Grygiel and Pierre Lescanne
Counting Terms in the Binary Lambda Calculus. (slides)
In a paper entitled \emph{Binary lambda calculus and combinatory logic}, John Tromp presents a simple way of encoding lambda calculus terms as binary sequences. In what follows, we study the numbers of binary strings of a given size that represent lambda terms and derive results from their generating functions, especially that the number of terms of size $n$ grows roughly like $1.963447954\ldots^n$.
14:30–15:00 Daniel Krenn and Stephan Wagner
The Number of Compositions into Powers of b. (slides)
For a fixed integer base $b\geq2$, we consider the number of compositions of~$1$ into a given number of powers of~$b$ and, related, the maximum number of representations a positive integer can have as an ordered sum of powers of~$b$. We study the asymptotic growth of those numbers and give precise asymptotic formulae for them, thereby improving on earlier results of Molteni. Our approach uses generating functions, which we obtain from infinite transfer matrices.
15:00–15:30 Clemens Heuberger, Sara Kropf and Helmut Prodinger
Asymptotic analysis of the sum of the output of transducers. (slides)
As a generalization of the sum of digits function and other digital sequences, we asymptotically analyze sequences defined as the sum of the output of a transducer when reading a random integer in $[0, N)$. Analogues in higher dimensions are also considered. We show that sequences defined by a certain class of recursions can be written in this framework. Depending on properties of the transducer, we give the main term, the periodic fluctuation and an error term of the expected value and the variance of this sequence. In many cases, the periodic fluctuation of the expected value is continuous and nowhere differentiable. We give a general formula for the Fourier coefficients of this periodic function. Furthermore, the sequence is asymptotically normally distributed for many transducers. As an example, we analyze the abelian complexity function of the paperfolding sequence, which has recently been studied by Madill and Rampersad.
15:30–16:00 Coffee Break
16:00–16:30 Daniel Krenn, Dimbinaina Ralaivaosaona and Stephan Wagner
On the Number of Multi-Base Representations of an Integer. (slides)
In a multi-base representation of an integer (in contrast to, for example, the binary or decimal representation) the base (or radix) is replaced by products of powers of single bases. The resulting numeral system is usually redundant, which means that each integer can have multiple different digit expansions. We provide a general asymptotic formula for the number of such multi-base representations of a positive integer $n$. Moreover, we prove central limit theorems for the sum of digits and the Hamming weight of a random representation.
16:30–17:00 Philippe Jacquet
Trie structure for Graph Sequences (slides)
We present a data structure extending trie structure, that we call {\it graph tries} that allows to store label functions defined on a graph. In this paper we analyze the performance of such structure (size, insertion costs) for labels in acyclic regular graphs such as infinite trees and lattices. We analyze means and variance of this parameters. We also show an interesting theorem that establishes the equivalence between dePoissonization and analytic continuation of coefficients.
17:00–17:30 AofA business meeting
18:00–19:00 LIP6 Colloquium, Donald Knuth (see here)

Wednesday, June 18

09:00–10:00 Manuel Kauers
Analysis of Summation Algorithms (Invited Talk) (slides)
In the context of AofA, summation algorithms have so far mainly been of interest as a tool for solving summation problems arising in the complexity analysis of some other algorithm. But it is also interesting to analyze the complexity of summation algorithms themselves, and to estimate the sizes of their output. In the talk, we will give an overview over some recent results in this direction.
10:00–10:30 Coffee Break
10:30–11:00 Stephen Melczer and Marni Mishna
Asymptotic lattice path enumeration using diagonals. (slides)
This work considers restricted lattice path models in any dimension such that the defining step set is highly symmetric. Combining the kernel method with multivariate generating function analysis, we determine general formulas for the dominant asymptotics of counting sequences of walks restricted to the first orthant. The step sets under consideration are symmetric with respect to each axis, which is a strong condition, however the resulting formulas are very straightforward. The exponential growth of each model is given by the number of steps, while the sub-exponential growth depends only on the dimension of the underlying lattice and the number of steps moving forward in each coordinate. These expressions are derived by analyzing the singular variety of a multivariate rational function whose diagonal counts the lattice paths in question.
11:00–11:30 Olivier Bernardi, Gwendal Collet and Eric Fusy
On the distance-profile of random rooted plane graphs. (slides)
We study the distance-profile of the random rooted plane graph $G_n$ with $n$ edges (by a plane graph we mean a planar map with no loops nor multiple edges). Our main result is that the profile and radius of $G_n$ (with respect to the root-vertex), rescaled by $(2n)^{1/4}$, converge to explicit distributions related to the Brownian snake. A crucial ingredient of our proof is a bijection we have recently introduced between rooted outer-triangular plane graphs and rooted eulerian triangulations, combined with ingredients from Chassaing and Schaeffer (2004), Bousquet-M\'elou and Schaeffer (2000), and Addario-Berry and Albenque (2013). Our convergence result for plane graphs implies similar convergence results for random rooted loopless and general maps.
11:30–12:00 Cyril Banderier and Michael Wallner
Some reflections on directed lattice paths. (slides)
This article analyzes \emph{directed lattice paths}, when a boundary reflecting or absorbing condition is added to the classical models. The lattice paths are characterized by two time-independent sets of rules (also called steps) which have a privileged direction of increase and are therefore essentially one-dimensional objects. Depending on the spatial coordinate, one of the two sets of rules applies, namely one for altitude $0$ and one for altitude bigger than $0$. The abscissa $y=0$ thus acts as a border which either absorbs or reflects steps. The absorption model corresponds to the model analyzed by Banderier and Flajolet (``Analytic combinatorics of directed lattice paths''), while the reflecting model leads to a more complicated situation. We show how the generating functions are then modified: the kernel method strikes again but here it unfortunately does not give a nice product formula. This makes the analysis more challenging, and, in the case of {\L}ukasiewicz walks, we give the asymptotics for the number of excursions, arches and meanders. Limit laws for the number of returns to 0 of excursions are given. We also compute the limit laws of the final altitude of meanders. The full analytic situation is more complicated than the Banderier--Flajolet model (partly because new ``critical compositions'' appear, forcing us to introduce new key quantities, like the drift at 0), and we quantify to what extent the global drift, and the drift at 0 play a r\^ole in the ``universal'' behavior of such walks.

Thursday, June 19

09:00–10:00 Christopher Moore
Les rendez-vous symétriques (Invited Talk) (slides)
You and a friend are trying to find each other in a park with n locations. Unfortunately, you don't have common names for these locations: you both call them 1,2,...,n, but your labels are scrambled by a uniform random permutation. If one of you stays put and the other explores (the so-called "wait for mommy" strategy) you will meet in expected time n/2, and this is optimal. But what if you haven't agreed in advance who should stay and who should explore? That is, what is the smallest expected time you can achieve if both players follow the same randomized strategy? In 1990, Anderson and Weber gave a strategy that succeeds in 0.829n expected time, but no one knows if this is optimal. I'll review this strategy and how it works, and then sketch a proof that any strategy requires at least 0.548n time. I'll then discuss possible paths to proving that the Anderson-Weber strategy is optimal; this would involve approximating the permanent of a matrix consisting mostly of 1s. This is joint work with Alex Russell.
10:00–10:30 Coffee Break
10:30–11:00 Michael Drmota and Emma Yu Jin
An Asymptotic Analysis of Unlabeled k-Trees. (slides)
In this paper we solve the {\it asymptotic counting problem} for unlabeled $k$-trees. By applying a proper singularity analysis of generating functions we show that the numbers $U_n$ of unlabeled $k$-trees of size $n$ are asymptotically given by $U_n \sim c_k n^{-5/2}\rho_{k}^{-n}$, where $c_k> 0$ and $\rho_{k}>0$ denotes the radius of convergence of the generating function $U(z)=\sum_{n\ge 0} U_n z^n$. Furthermore we prove that the number of {\it leaves} and more generally the number of {\it nodes} of given degree satisfy a central limit theorem with mean value and variance that are asymptotically linear in the number of hedra where a hedron is a $(k+1)$-clique in a $k$-tree.
11:00–11:30 Michael Drmota, Michael Fuchs and Yi-Wen Lee
Limit Laws for the Number of Groups formed by Social Animals under the Extra Clustering Model. (slides)
We provide a complete description of the limiting behaviour of the number $X_n$ of groups that are formed by social animals when the number $n$ of animals tends to infinity. The analysis is based on a random model by Durand, Blum and Fran\c{c}ois, where it is assumed that groups are formed more likely by animals which are genetically related. The random variable $X_n$ can be described by a stochastic recurrence equation that is very similar to equations that occur in the stochastic analysis of divide-and-conquer algorithms although it does not fall into already known cases. In particular, we obtain (in the most interesting) ``neutral model'' a curious central limit theorem, where the normalizing factor is $\sqrt{{\rm Var}(X_n)/2}$. In the non-neutral (or extra clustering) cases the results are completely different. We obtain either a mixture of a discrete and a continuous limit law or just a discrete limit law.
11:30–12:00 Chung-Kuei Lee
The k-th Total Path Length and the Total Steiner k-Distance for Digital Search Trees (slides)
The total Steiner $k$-distance and the $k$-th total path length are the sum of the size of Steiner trees and ancestor-trees over sets of $k$ nodes of a given tree, respectively. They are useful statistics with many applications. Consequently, they have been analyzed for many different random trees, including increasing trees, binary search trees, generalized $m$-ary search trees and simply generated trees. In this paper, we investigate the two parameters for digital search trees, which are fundamental data structures in computer science with wide applications. We derive the means, covariances and variances for the total Steiner $k$-distances and the $k$-th total path lengths by the "Poisson-Laplace-Mellin Method". Moreover, results about the limiting distributions are obtained as well.
12:00–14:00 Lunch
14:00–14:30 Svante Janson
Asymptotic normality of fringe subtrees and additive functionals in conditioned Galton--Watson trees. (slides)
We consider conditioned Galton--Watson trees and show asymptotic normality of additive functionals that are defined by toll functions that are not too large. This includes, as a special case, asymptotic normality of the number of fringe subtrees isomorphic to any given tree, and joint asymptotic normality for several such subtree counts. The offspring distribution defining the random tree is assumed to have expectation 1 and finite variance; no further moment condition is assumed.
14:30–15:00 Cecilia Holmgren and Svante Janson
Using Stein's method to show Poisson and normal limit laws for fringe subtrees. (slides)
We consider sums of functions of fringe subtrees of binary search trees and random recursive trees (of total size $ n $). The use of Stein's method and certain couplings allow provision of simple proofs showing that in both of these trees, the number of fringe subtrees of size $k<n$, where $k\rightarrow \infty$, can be approximated by a Poisson distribution. Combining these results and another version of Stein's method, we can also show that for $ k=o(\sqrt{n}) $, the number of fringe subtrees in both types of random trees has asymptotically a normal distribution as $n\rightarrow \infty$. Furthermore, using the Cram\'er--Wold device, we show that a random vector with components corresponding to the random number of copies of certain fixed fringe subtrees $ T_i $, has asymptotically a multivariate normal distribution. We can then use these general results on fringe subtrees to obtain simple solutions to a broad range of problems relating to random trees; as an example, we can prove that the number of protected nodes in the binary search tree has asymptotically a normal distribution.
15:00–15:30 Rudolf Gruebel
Persisting randomness in randomly growing discrete structures: graphs and search trees. (slides)
The successive discrete structures generated by a sequential algorithm from random input constitute a Markov chain that may exhibit long term dependence on its first few input values. Using examples from random graph theory and search algorithms we show how such persistence of randomness can be detected and quantified with techniques from discrete potential theory. We also show that this approach can be used to obtain strong limit theorems in cases where previously only distributional convergence was known.
15:30–16:00 Coffee Break
16:00–16:30 Joachim Buhmann, Alexey Gronskiy and Wojciech Szpankowski
Free Energy Rates for a Class of Very Noisy Optimization Problems. (slides)
We study a class of stochastic optimization problems for which the cardinality of the set of feasible solutions (called also configurations) $m$ and the size of every feasible solution $N$ satisfy $\log m=o(N)$. Assuming the data to be random, e.g., weights of a graph, edges in spanning tree problem, elements of matrices in assignment problem, etc. fluctuate due to measurements, we adopt the maximum entropy framework by weighting solutions with a Boltzmann distribution where the inverse computational temperature $\b$ controls the cost resolution of the solution space. Large fluctuations of the costs due to high input randomness correspond to a low cost resolution $\b$. For such a high noise level in the instances implying low $\b$, we estimate the free energy in the asymptotic limit. This quantity plays a significant role in many applications, including algorithm analysis, robust optimization and so on. In particular, we prove that the free energy exhibits a phase transition in the second order term.
16:30–17:00 Eugenijus Manstavicius and Vytautas Stepanauskas
On variance of an additive function with respect to a generalized Ewens probability (slides)
An additive function defined on the symmetric group is a sum of dependent random variables when a permutation is taken according to a generalized Ewens probability. We establish an upper bound of its variance via a sum of variances of the summands. The idea of our approach goes back to a paper by A. Bir\'o and T. Szamuely generalizing the Tur\'an-Kubilius inequality for number-theoretic functions.
17:00–17:45 Hsien-Kuei Hwang et al.
(slides) and (more slides)
19:00– Dinner

Friday, June 20

09:00–10:00 Marc Noy
Logical limit laws in combinatorics (Invited Talk) (slides)
Let A be a class of combinatorial structures equipped, for each N, with a probability distribution on the collection of objects of size N. Given a sentence S in some logical language, we are interested in the limiting probability P(S) that S is satisfied among all objects of size N, as N goes to infinity. If P(S) is either 0 or 1 for each sentence S, we say that the zero-one law holds. The first result of this kind was obtained by Glebskii et al. in 1969 for the class of labelled graphs and sentences in first order logic (FO). Compton (1987) obtained in some cases zero-one laws solely from properties of the counting function of the class A. Later he extended it to monadic second order logic (MSO), which is FO logic plus quantification over unary relations. More recently McCoy (2002) proved a zero-one law in MSO logic for labelled trees. We provide a significant extension of McCoy’s result to classes of graphs closed under taking minors. As an example, we prove the MSO zero-one law for connected planar graphs and a convergence law (every sentence has a limit, not necessarily 0 or 1) for all planar graphs. We also determine the closure of the set of all possible limiting probabilities, both in FO and MSO. For the proofs we use classical tools from combinatorial logic, in particular Ehrenfeucht-Fraïssé games, and properties of random graphs from a minor-closed class.
10:00–10:30 Coffee Break
10:30–11:00 Kevin Leckey, Ralph Neininger and Henning Sulzbach
Analysis of Radix Selection on Markov Sources. (slides)
The complexity of the algorithm Radix Selection is considered for independent data generated from a Markov source. The complexity is measured by the number of bucket operations required and studied as a stochastic process indexed by the ranks; also the case of a uniformly chosen rank is considered. The orders of mean and variance of the complexity and limit theorems are derived. We find weak convergence of the appropriately normalized complexity towards a Gaussian process with explicit mean and covariance functions (in the space $\Do$ of c{\`a}dl{\`a}g functions on $[0,1]$ with the Skorokhod metric) for uniform data and the asymmetric Bernoulli model. For uniformly chosen ranks and uniformly distributed data the normalized complexity was known to be asymptotically normal. For a general Markov source (excluding the uniform case) we find that this complexity is less concentrated and admits a limit law with non-normal limit distribution.
11:00–11:30 Arvind Ayyer, Jérémie Bouttier, Sylvie Corteel and François Nunzi
Multivariate juggling probabilities. (slides)
We consider refined versions of Markov chains related to juggling. We further generalize the construction to juggling with arbitrary heights as well as infinitely many balls, which are expressed more succinctly in terms of Markov chains on integer partitions. In all cases, we give explicit product formulas for the stationary probabilities and closed-form expressions for the normalization factor. We also refine and generalize enriched Markov chains on set partitions. Lastly, we prove that in one case, the stationary distribution is attained in finite time.
11:30–12:00 Pawel Hitczenko and Amanda Parshall
On the distribution of parameters in random weighted staircase tableaux. (slides)
In this paper, we study staircase tableaux, a combinatorial object introduced due to its connections with the asymmetric exclusion process (ASEP) and Askey-Wilson polynomials. Due to their interesting connections, staircase tableaux have been the object of study in many recent papers. More specific to this paper, the distribution of various parameters in random staircase tableaux has been studied. There have been interesting results on parameters along the main diagonal, however, no such results have appeared for other diagonals. It was conjectured that the distribution of the number of symbols along the $k$th diagonal is asymptotically Poisson as $k$ and the size of the tableau tend to infinity. We partially prove this conjecture; more specifically we prove it for the second main diagonal.
12:00–14:00 Lunch
14:00–15:00 Gilles Schaeffer
Simple branched covers and planar maps: Cayley vs Catalan (Invited Talk)
In the last 15 years a tight relation between planar maps and trees has emerged, leading to great progress in the study of large random planar maps and their continuum limit, the Brownian map. All these results belong to the "Catalan realm" of simple varieties of ordered trees, with algebraic ordinary generating functions. But this Catalan realm admits a parallel world, the "Cayley realm", where many results can be reproduced with ordered structures replaced by labelled structures, and ordinary generating functions replaced by exponential generating functions. We identify simple branched covers as the natural Cayley analogs of planar maps, and examine how the bijective machinery that was developed for maps applies in this context. This leads to bijective proofs and new results for double Hurwitz numbers. Based on join work with Enrica Duchi and Dominique Poulalhon.
15:00–15:30 Juanjo Rué and Kerstin Weller
The Ising model on graphs: grammar and applications to bipartite enumeration. (slides)
We adapt the grammar introduced by Chapuy, Fusy, Kang and Shoilekova to study the Ising model on graphs which are defined by their $3$-connected components. This approach permits to encode simultaneously counting formulas for the graph family under study as well as the generating function for the corresponding bipartite family of graphs. In particular, using our approach it is possible to avoid the often encountered difficult integration step which appears when relating the generating function of networks and the generating function of 2-connected graphs. As a first application of our method, we asymptotically enumerate labelled bipartite series-parallel graphs with $n$ vertices, and we study the probability that a bipartite series-parallel graph of size $n$ chosen uniformly at random from all object of size $n$ is connected.
15:30–16:00 Amalia Duch, Gustavo Lau and Conrado Martínez
On the Average Performance of Fixed Partial Match Queries in Random Relaxed K-d Trees. (slides)
We obtain an explicit formula for the expected cost of a fixed partial match query in a random relaxed $K$-d tree, that is, the expected cost for a query of the form \[ q=(q_0,q_1,\ldots,q_{K-1}) \] with $0 < s < K$ specified coordinates with values $z_0, \ldots, z_{s-1}\in (0,1)$. This is a generalization of previous results in the literature for $s=1$. Qualitatively similar results hold for standard $K$-d trees and we conjecture that this also holds for other multidimensional tree structures such as quadtrees and $K$-d tries.
16:00– Coffee Break

Valid XHTML 1.0! CSS Valide !