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 onepage pdf file is available here.
Click here for the GROUP PHOTO!
08:30–09:00  Welcome 
09:00–10:00 
Problems Philippe Would Have Liked (Flajolet Lecture)
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 
Anticipated rejection algorithms and the DarlingMandelbrot distribution.
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 socalled
DarlingMandelbrot distribution, studied by Darling (1952) and Lew (1994). We
also give an explicit form to the density of the DarlingMandelbrot
distribution and derive some of its analytic properties.

11:00–11:30 
A LinearTime Algorithm for Sampling Graphs with Given Degrees.
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 
Pivot Sampling in DualPivot Quicksort – Exploiting Asymmetries in Yaroslavskiy’s Partitioning Scheme
The new dualpivot 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 singlepivot 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 
A unified approach to linear probing hashing.
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 
Efficiently Navigating a Random Delaunay Triangulation.
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 
Analytic combinatorics of chord and hyperchord diagrams with k crossings.
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 crossingfree 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 
No Shannon effect induced by And/Or trees.
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 
09:00–10:00 
Random graphs from a minorclosed class (Invited Talk)
Consider a minorclosed 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 
Connectivity for a modified binomial random graph by agglomeration.
In the classical Erd\H osR\'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 osR\'enyi model. We consider an initial configuration of subsets of vertices and we call each subset a supervertex, then the random graph model is defined by letting two supervertices 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 
On Symmetry of Uniform and Preferential Attachment Graphs.
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 
Choices and Intervals.
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 sizebiased empirical distribution evolves in the limit according to a certain deterministic evolution equation. Although this equation involves a nonlocal, nonlinear operator, it can be studied thanks to a carefully chosen norm with respect to which this operator is contractive.
In finitedimensional 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 infinitedimensional setting.

12:00–14:00  Lunch 
14:00–14:30 
Counting Terms in the Binary Lambda Calculus.
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 
The Number of Compositions into Powers of b.
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 
Asymptotic analysis of the sum of the output of transducers.
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 
On the Number of MultiBase Representations of an Integer.
In a multibase 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
multibase 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 
Trie structure for Graph Sequences
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) 
09:00–10:00 
Analysis of Summation Algorithms (Invited Talk)
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 
Asymptotic lattice path enumeration using diagonals.
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 subexponential 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 
On the distanceprofile of random rooted plane graphs.
We study the distanceprofile 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 rootvertex),
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 outertriangular plane graphs and
rooted eulerian triangulations, combined with ingredients from Chassaing and Schaeffer (2004),
BousquetM\'elou and Schaeffer (2000), and AddarioBerry and Albenque (2013).
Our convergence result for plane graphs implies similar convergence results for random
rooted loopless and general maps.

11:30–12:00 
Some reflections on directed lattice paths.
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 timeindependent sets of rules (also called steps)
which have a privileged direction of increase and are therefore essentially onedimensional 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 BanderierFlajolet 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.

09:00–10:00 
Les rendezvous symétriques (Invited Talk)
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 socalled "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 AndersonWeber 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 
An Asymptotic Analysis of Unlabeled kTrees.
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 
Limit Laws for the Number of Groups formed by Social Animals under the Extra Clustering Model.
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 divideandconquer 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 nonneutral (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 
The kth Total Path Length and the Total Steiner kDistance for Digital Search Trees
The total Steiner $k$distance and the $k$th total path length are the sum of the size of Steiner trees and ancestortrees 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 "PoissonLaplaceMellin Method". Moreover, results about the limiting distributions are obtained as well.

12:00–14:00  Lunch 
14:00–14:30 
Asymptotic normality of fringe subtrees and additive functionals in conditioned GaltonWatson trees.
We consider conditioned GaltonWatson 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 
Using Stein's method to show Poisson and normal limit laws for fringe subtrees.
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\'erWold 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 
Persisting randomness in randomly growing discrete structures: graphs and search trees.
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 
Free Energy Rates for a Class of Very Noisy Optimization Problems.
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 
On variance of an additive function with respect to a generalized Ewens probability
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\'anKubilius inequality for numbertheoretic functions.

17:00–17:45  
19:00–  Dinner 
09:00–10:00 
Logical limit laws in combinatorics (Invited Talk)
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 zeroone 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 zeroone 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 zeroone 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 zeroone 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 EhrenfeuchtFraïssé games, and properties of random graphs from a minorclosed class.

10:00–10:30  Coffee Break 
10:30–11:00 
Analysis of Radix Selection on Markov Sources.
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 nonnormal limit distribution.

11:00–11:30 
Multivariate juggling probabilities.
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 closedform 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 
On the distribution of parameters in random weighted staircase tableaux.
In this paper, we study staircase tableaux, a combinatorial object
introduced due to its connections with the asymmetric
exclusion process (ASEP) and AskeyWilson 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 
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 
The Ising model on graphs: grammar and applications to bipartite enumeration.
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 2connected graphs.
As a first application of our method, we asymptotically enumerate labelled bipartite seriesparallel graphs with $n$ vertices, and we study the probability that a bipartite seriesparallel graph of size $n$ chosen uniformly at random from all object of size $n$ is connected.

15:30–16:00 
On the Average Performance of Fixed Partial Match Queries in Random Relaxed Kd Trees.
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_{K1})
\]
with $0 < s < K$ specified coordinates with values
$z_0, \ldots, z_{s1}\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 