Last modified: June 15, 2009. 14:15:17 pm
List of talks
 AddarioBerry, Louigi: Prim's algorithm, critical percolation, and infinite subtrees of finite trees
 Aguech, Rafik: The Moran Model, height of random walks and analysis of a cache algorithm
 Banderier, Cyril: Average Case Analysis of NPcomplete Problems: Maximum Independent Set and Exhaustive Search Algorithms
 Baryshnikov, Yuliy: Elliptic curves and frozen regions in fortresses
 Bouttier, jérémie: Metric properties of large random planar maps
 Chauvin, Brigitte: Limit distributions for P\'olya urns
 David, Julien: On the average complexity of Moore's state minimization algorithm
 Drmota, Michael: (Un)Expected Behavior of the Digital Search Tree Profile
 Fill, Jim: The numbers of symbol comparisons used by QuickSelect and by QuickSort (Limiting Distributions)
 Flajolet, Philippe: The numbers of symbol comparisons used by QuickSelect and by QuickSort (Overview)
 Flajolet, Philippe: Discrete Buffon Machines and Numbers
 Fusy, Eric: A combinatorial method for counting planar graphs
 Gittenberger, Bernahrd: On the Moments of the Area below Lattice Paths
 Gnedin, Sasha: Small counts in the infinite occupancy scheme
 Grübel, Rudolf: On the subtree size profile of binary search trees
 Heuberger, Clemens: Digit Distribution in Positional Number Systems with Digits Forming an Arithmetic Progression
 Holmes, Susan: Random threshold graphs, their limits and applications
 Holmgren, Cecilia: Characteristics of Split Trees by use of Renewal Theory
 Hwang, HseinKuei: Psiseries method in random trees and moments of high orders
 Jacquet, Philippe: Information propagation speed in DTN
 Janson, Svante: Some applications of renewal theory to the analysis of algorithms
 Lladser, Manuel: A new approach to population diversity: the extrapolation problem
 Louchard, Guy: Asymptotic independence of Uniform Markov chains
 Mahmoud, Hosam: Gaussian phases in generalized coupon collection
 Nebel, Markus: Maximum Likelihood Analysis of Algorithms
 Noy, Marc: Asymptotic properties of graphs of given genus
 Roesler, Uwe: The Weighted Branching Process and Stochastic Fixed Points
 Sankoff, David: Gene order, gene clusters and random graphs
 Schaeffer, Gilles: TBA
 Soria, Michèle: Limiting Distribution for Distances in $k$trees and other graphs
 Szpankowski, Wojciech: On a nonprefix code and its analysis
 Vallée, Brigitte: The number of symbol comparisons used by QuickSelect and by QuickSort
 van Leeuwaarden, Johan: Singularity analysis through functional equations for random walks in the quarter plane
 Wilf, Herbert: Some new asymptotic problems in partition theory
Abstracts
 Speaker: AddarioBerry, Louigi  McGill University
 Title:Prim's algorithm, critical percolation, and infinite subtrees of finite trees

Abstract:
(joint work with Simon Griffiths and Ross Kang).
Let G be a finite or infinite connected rooted graph and assign independently to each edge of G a random weight w_{e} with distribution Unif[0,1]. The invasion percolation cluster is the tree T grown inside G as follows: start with the root, add the lowest weight edge leaving the root, then at each step thereafter add the lowest weight edge leaving the current tree. When applied to finite weighted graphs this procedure is the well known Prim's algorithm for growing a minimum weight spanning tree. Less is known about invasion percolation on infinite graphs; it is a subject of current research. We study invasion percolation on Aldous' Poissonweighted infinite tree, which may be viewed as a limit of invasion percolation on either the complete graph K_{n} (as n→∞) or the dary infinite tree (as d→∞). Furthermore, this limit picture, which may be obtained via a Poisson point process on the upper right quadrant [0,∞)×[0,∞), provides a suitable setting for short proofs of many interesting properties. We also define a related stationary process which can be seen as capturing the behaviour of invasion percolation far from its starting point. This behaviour is closely linked with that of critical bond percolation, and so serves as an example of selforganised criticality.
 Speaker: Aguech, Rafik  Faculté des Sciences de Monastir (Tunisia)
 Title:The Moran Model, height of random walks and analysis of a cache algorithm

Abstract:
Joint work with C. Banderier
 Speaker: Banderier, Cyril  LIPN  Univ. Paris 13
 Title:Average Case Analysis of NPcomplete Problems: Maximum Independent Set and Exhaustive Search Algorithms

Abstract:
In this talk, we deal with rigorous average case analysis of NP complete problems, relying on some mathematical tools from complex analysis and probability theory. We consider here one of the historical prototype of such problems: Maximum Independent Set (MIS).
For a large class of exhaustive algorithms which always find exactly a MIS, their complexity is directly related to their number of iterations. Under the Γ(n,m) and G(n,p) distribution for graphs, we give some fascinating phase transitions between exponential (A^{n}), superpolynomial (n^{lnn}), and polynomial (n^{d}) average complexities.
Our approach gives a precise picture of the "complexity landscape" of these algorithms, depending on the average degree (or the ratio vertices/edges) of the graph, and gives access to the location of the "hard regions" where people could then sample their inputs if they want to make some benchmarks (may it be for the worst or average case).
The challenging associated mathematical aspects force us to introduce new analyses (for a large class of recurrences), which will clearly be of interest for many other NP hard problems (typically, optimization problems on graphs).
Direct applications cover graph 3coloring (which is also a deep motivation for considering our class of exhaustive TarjanChvàtal like algorithms), and numerous constraint satisfaction problems.
Joint work with HsienKuei Hwang, Vlady Ravelomanana, Vytas Zacharovas.
 Speaker: Baryshnikov, Yuliy  Bell Labs, USA
 Title:Elliptic curves and frozen regions in fortresses

Abstract:
The diabolo tilings of fortresses (or, equivalently, appropriately weighted complete matchings in a family of bipartite graphs) were introduced and studied by Propp and his collaborators. They exhibited frozenmoderate transition similar to that seen in Aztec diamonds, but far more complicated. Using Wulff construction (i.e. entropic approach), Kenyon and Okounkov proved the conjectured by Cohn and Pemantle formula for the frozen region boundary. Here, we give an alternative derivation for the boundary of the frozen region and determine the densities in the moderate region, basing on our with Pemantle recent results on asymptotics of multivariate generating function.
 Speaker: Bouttier, jérémie  CEA, France
 Title:Metric properties of large random planar maps

Abstract:
In this talk, we mainly consider planar quadrangulations that form a particular class of maps. When equipped with the graph distance, these may be viewed as metric spaces. We wish to understand their statistical properties under the uniform measure over maps of given size. In the limit of large size, we expect to obtain asymptotic results which are independant of the particular class of maps under consideration, and which characterize their universal scaling limit, the Brownian map.
We shall review a number of metric properties of large random quadrangulations. Their derivation rely on the Schaeffer bijection between quadrangulations and welllabeled trees, or its suitable generalizations, and on a remarkable "integrability" property which leads to explicit expressions for the associated generating functions.
If time allows, I shall briefly discuss statistical physics models on random maps (such as the Ising model), in which we expect to find different universal scaling limits, but where many steps are missing.
This talk is based on joint work with Emmanuel Guitter and earlier work with Philippe Di Francesco.
 Speaker: Chauvin, Brigitte  LMV Univ. Versailles \& Inria Rocquencourt
 Title:Limit distributions for P\'olya urns

Abstract:
The talk focuses on a work in progress together with Nicolas Pouyanne, in order to identify limit distributions for some Pólya urns. In a first part, the definition and some historical examples are given (Ehrenfest urn, original Pólya urn, ...), with emphasis on Pólya urns coming from analysis of algorithms, especially those related to random trees (recursive trees, mary search trees, ...). A particular attention is paid to the phase transition which appears in the limit distributions introducing a distinction between "small" and "large" urns.
In the main part, a two colors Pólya urn is considered. Assume it is balanced (i.e. the same number S of balls are added at each draw) and assume it is a ``large'' urn (i.e. σS, the second eigenvalue of the replacement matrix satisfies S/2 < σS ≤ S). After n drawings, the composition vector has asymptotically a first deterministic term of order n and a second random term of order n^{σ}. The goal is to catch the limit distribution of this random term.
The method consists in embedding the discrete urn in continuous time, getting thus a multitype branching process. Writing the dislocation equations for this process gives a system of differential equations on the Fourier transforms of the limit distributions. The resolution is carried out and it turns out that the Fourier transforms are explicitely related to Abelian integrals on a Fermat curve.
Some properties of these limit distributions are explored: do they have moments of any order? Are they infinitely divisible? Are they stable? Are they determined by their moments? Do they have a density? Are the tails heavy or not?
Answers:
yes; yes; no; open question; yes; probably between.The same method is applied to mary search trees, in the case when m ≥ 27, i.e. when the corresponding urn is "large" (meaning that the second eigenvalues of the replacement matrix are large: their real part σ satisfies 1/2 < σ ≤ 1). We obtain a system of m−1 integrodifferential equations, related to the non linear equation y^{(m−1)}=y^{m}.
 Speaker: David, Julien  LIGM, Univ. Paris Est
 Title:On the average complexity of Moore's state minimization algorithm

Abstract:
Thanks to good algorithmic properties, deterministic finite automata are often used to represent regular languages in a computer. The minimal automaton of such a language is the unique smallest automaton that regognizes it. In the worst case scenario the best known algorithm computes the minimal automaton in a time complexity bounded by $O(n \log n)$. We prove that another algorithm, due to Moore, which is a lot simpler to implement but often ignored because of its worst case complexity in $O(n^2)$, has an average complexity bounded by $O(n log n)$. In collaboration with F. Bassino and C. Nicaud.
 Speaker: Drmota, Michael  TU Wien, Institute of Discrete Mathematics and Geometry
 Title:(Un)Expected Behavior of the Digital Search Tree Profile

Abstract:
In collaboration with Wojciech Szpankowski.
A digital search tree (DST)  one of the most fundamental data structure on words  is a digital tree in which keys (strings, words) are stored directly in (internal) nodes. Such trees find myriad of applications from the popular LempelZiv'78 data compression scheme to distributed hash tables. The profile of a DST measures the number of nodes at the same distance from the root; it is a function of the number of stored strings and the distance from the root. Most parameters of DST (e.g., height, fillup) can be expressed in terms of the profile. However, from the inception of DST, the analysis of the profile has been elusive and it has become a prominent open problem in the area of analysis of algorithms. We make here the first, but decisive step, towards solving this problem. We present a precise analysis of the average profile when stored strings are generated by a biased memoryless source. The main technical difficulty of analyzing the profile lies in solving a sophisticated recurrence equation. We present such a solution for the Poissonized version of the problem (i.e., when the number of stored strings is generated by a Poisson distribution) in the Mellin transform domain. To accomplish it, we introduce a novel functional operator that allows us to express the solution in an explicit form, and then using analytic algorithmics tools to extract asymptotic behavior of the profile. This analysis is surprisingly demanding but once it is carried out it reveals unusually intriguing and interesting behavior. The average profile undergoes several phase transitions when moving from the root to the longest path. At first, it resembles a full tree until it abruptly starts growing polynomially and it oscillates in this range. Our results are derived by methods of analytic algorithmics such as generating functions, Mellin transform, Poissonization and dePoissonization, the saddlepoint method, singularity analysis and uniform asymptotic analysis.
 Speaker: Fill, Jim  The Johns Hopkins University, Department of Applied Mathematics and Statistics
 Title:The numbers of symbol comparisons used by QuickSelect and by QuickSort (Limiting Distributions)

Abstract:
See abstract in common with Brigitte Vallée (and also Philippe Flajolet).
 Speaker: Flajolet, Philippe  Inria, Algorithms
 Title:The numbers of symbol comparisons used by QuickSelect and by QuickSort (Overview)

Abstract:
See abstract in common with Brigitte Vallée (and also Jim Fill).
 Speaker: Flajolet, Philippe  Inria, Algorithms
 Title:Discrete Buffon Machines and Numbers

Abstract:
Generalizing the wellknown Buffon experiment, we ask ourselves which probability distributions can be generated exactly from a source of unbiased coin flips. We shall describe and analyse a few simple Buffon machines that can generate geometric, Poisson, and logarithmicseries distributionsthese are required to transform continuous Boltzmann samplers into discrete random generators of classical combinatorial structures. Say that a number is Buffon if it is the probability of success of a simple probabilistic experiment based on discrete coin flips. We shall also provide humanaccessible Buffon machines, which require a dozen coin flips or less, on average, and produce experiments whose probabilities are expressible in terms of numbers such as π, log2, exp(−1), ζ(3).
(Based on joint work with Michele Soria and Maryse Pelletier.)
 Speaker: Fusy, Eric  LIX, Polytechnique, France
 Title:A combinatorial method for counting planar graphs

Abstract:
Giménez and Noy have given recently a complete analytic solution to the problem of counting planar graphs. As a crucial step they calculate implicit analytic expressions for the series counting planar graphs. We present a new method for finding such an expression, which avoids the technical integration steps addressed by Giménez and Noy. The two main ingredients are a bijection due to Bouttier, Di Francesco and Guitter for counting vertexpointed planar maps, as well as a decomposition grammar (with minus signs) obtained by translating a classical decomposition (formalised by Tutte) of a graph into 3connected components.
 Speaker: Gittenberger, Bernahrd  TU Wien, Institute for Discrete Math. and Geometry
 Title:On the Moments of the Area below Lattice Paths

Abstract:
We study the moments of the area below directed lattice paths, i.e., walks on the integers with jumps from an a priori given finite set of integers. The focus is on enumerative results obtained by means of generating functions and the kernel method. First we study excursions and meanders of simple paths, where the roots of the kernel have a somewhat simpler structure, and give full asymptotics of average and variance. Then we present some investigations on on more complicated walks which is work in progress. It is possible to obtain represetations for the generating functions of all factorial moments in terms of certain roots of the kernel.
 Speaker: Gnedin, Sasha  Utrecht University
 Title:Small counts in the infinite occupancy scheme

Abstract:
The paper is concerned with the classical occupancy scheme with infinitely many boxes, in which n balls are thrown independently into boxes 1,2,..., with probability p_{j} of hitting the box j, where p_{1} ≥ p_{2} ≥ ... > 0 and $\sum_{j=1}^\infty p_j=1$. We establish joint normal approximation as n→∞ for the numbers of boxes containing r_{1},r_{2},...,r_{m} balls, standardized in the natural way, assuming only that the variances of these counts all tend to infinity. The proof of this approximation is based on a dePoissonization lemma. We then review sufficient conditions for the variances to tend to infinity. Typically, the normal approximation does not mean convergence. We show that the convergence of the full vector of rcounts only holds under a condition of regular variation, thus giving a complete characterization of possible limit correlation structures.
Joint work with A. D. Barbour.
 Speaker: Grübel, Rudolf  Leibniz Universitaet Hannover, Germany
 Title:On the subtree size profile of binary search trees

Abstract:
For random trees T generated by the binary search tree algorithm from uniformly distributed input we consider the subtree size profile, which maps k ∈ N to the number of nodes in T that root a subtree of size k. Complementing earlier work by Devroye (1991), by Feng, Mahmoud and Panholzer (2008), and by Fuchs (2008), we obtain results for the range of small kvalues and the range of kvalues proportional to the size n of T. In both cases emphasis is on the process view, i.e. the joint distributions for several kvalues. Regarding the dynamics of the tree sequence we find a qualitative difference between the asymptotic behaviour of the small and large range of the profile.
The talk is based on joint work with Florian Dennert, and with Steve Evans and Anton Wakolbinger.
 Speaker: Heuberger, Clemens  TU Graz
 Title:Digit Distribution in Positional Number Systems with Digits Forming an Arithmetic Progression

Abstract:
We consider digit expansions to a positive integer base b ≥ 2 with positive digits forming an arithmetic progression, whose common difference is coprime to the base. Since in general, this is not sufficient to represent all positive integers, the most significant digit is allowed to belong to a certain larger set of possible digits. We do not require zero to be an admissible digit.
The motivation for studying these digit expansions comes from a quite surprising answer to a graph theoretic optimisation problem: For a given number n of vertices, the unique graph with maximum degree 3 with the largest number of independent vertex subsets can be described by using a binary expansion of n+1 using the digits 1 and 4 (and additionally, the digit 2 is allowed in the most significant position). For higher maximum degrees, higher bases and other arithmetic progressions arise.
The obvious question that comes to mind is how the digits are distributed, among, say, the first N integers. To answer this, the MellinPerron technique is used. But an even simpler question which isn't really a question for the standard bary system, say, must be addressed: the length of the representation! In general, the length is not a monotone function anymore, and a larger number may have a shorter representation!
In base b, the length of the standard representation (index of the leading digit) of n is given by log_{b}n . Similar formulæ are given in our case, but with several terms, all expressed with floor functions.
We give explicit formulæ for length and digits, we also study the averages and obtain asymptotic results involving periodic functions that are completely described via their Fourier coefficients.
(based on joint work with H. Prodinger and St. Wagner)
 Speaker: Holmes, Susan  Stanford University
 Title:Random threshold graphs, their limits and applications

Abstract:
I will present a limit theory of large threshold graphs and apply this to a variety of models for random threshold graphs. The results give a nice set of examples of this special class of graphs which have an underlying variable, very useful in applications. Graphs have important applications in modern systems biology and social sciences. Edges are created between interacting genes or people who know each other. However graphs are not objects which are naturally amenable to simple statistical analyses, there is no natural average graph for instance. Being able to predict or replace a graph by hidden (statisticians call them latent) real variables has many advantages. This talk studies such a class of graphs, that sits within the larger class of interval graphs itself a subset of intersection graphs.
This is joint work with Persi Diaconis and Svante Janson.
 Speaker: Holmgren, Cecilia  Uppsala Univ., Sweden
 Title:Characteristics of Split Trees by use of Renewal Theory

Abstract:
We investigate some characteristics of random split trees introduced by Devroye; split trees include for example binary search trees, mary search trees, quadtrees, median of (2k+1)trees, simplex trees, tries and digital search trees. More precisely: We introduce renewal theory, and use this theory to prove several results about split trees. A split tree of cardinality N is constructed by distributing N "balls" (which often represent some "key numbers") in a subset of vertices of an infinite tree. One of our main result is to give a relation between the deterministic number of balls N and the random number of vertices n. Devroye has shown that there is a central limit law for the depth of the last inserted ball so that most vertices are close to lnN/μ+O(√ lnN), where μ is some constant depending on the type of split tree; we sharpen this result by finding an upper bound for the expected number of vertices with depths ≥ lnN/μ+ln^{0.5+ε} N or depths ≤ lnN/μ+ln^{0.5+ε} N for some arbitrary constant ε > 0. We also find the first asymptotic of the variances of the depths of the balls in the tree.
 Speaker: Hwang, HseinKuei  Academia Sinica, Taiwan
 Title:Psiseries method in random trees and moments of high orders

Abstract:
An unusual and surprising lacunary asymptotic expansion is derived of the probability that two randomly chosen binary search trees are identical. A similar quantity also arises in the analysis of phylogenetic trees. The approach we use to attack the nonlinear differential equation is new in the analysis of algorithms and relies on the socalled psiseries method. Such an expansion turns out to be the tip of an iceberg and we show that similar lacunarytype asymptotic expansions also appear in other random trees of logarithmic height and in the asymptotics of higher moments of some problems in discrete probability and statistical physics. (This talk is based on joint work with HuaHua Chern and Conrado Martinez.)
 Speaker: Jacquet, Philippe  EPI Hipercom, INRIA, France
 Title:Information propagation speed in DTN

Abstract:
We analyze the performance of epidemic routing in largescale intermittently connected networks, under a random geometric graph model and for different mobility parameters (such as the randomwaypoint, random walk and Brownian motion models). We assume that packet transmission and propagation are instantaneous within a fixed radio range. We derive a generic scaling law on the delay which provides us with lower bounds: the average delay froma source to a destination and the average broadcast delay are both at least proportional to the square root of n times the ratio of the radio range over node speed, where n is the number of nodes in the network for a given normalized density. This result disproves the conjecture of a delay proportional to logn/n times meeting rate which was obtained from previous models based on an ErdosRenyi graph model evolution. The average meeting rate is proportional to the node speed times radio range divided by the node density.
The analysis is based on a continuous spacetime information path density upperbound and segmentation,Poissonization and dePoissonization over the number of nodes , and Laplace transform singularity analysis.
 Speaker: Janson, Svante  Uppsala Univ., Sweden
 Title:Some applications of renewal theory to the analysis of algorithms

Abstract:
I will show how some wellknown results from renewal theory (including results by myself) can be used in AofA. Examples include applications to random digital search trees and to Khodak codes.
 Speaker: Lladser, Manuel  Univ. of Colorado, USA
 Title:A new approach to population diversity: the extrapolation problem

Abstract:
Consider an urn with colored balls but with an unknown composition i.e. you do not know what are the specific colors in the urn nor their relative proportions. To learn about its composition imagine sampling balls with replacement out of the urn. The urn models a variety of situations of practical interest. For instance, the different colors in the urn could represent different solutions to a particular binding site problem in an RNA pool, or the different species of bacteria present in a section of soil. In rich environments like these even the most exhaustive data cannot saturate sampling and the traditional tools to estimate alphadiversity (i.e. the total number of species or other taxonomic units present in the environment) provide inaccurate results. This motivates to reformulate the problem in terms of the fraction of the population that belongs to unseen classes. During my talk I will show that this last quantity cannot be predicted once the sample size has been fixed. Instead, using randomized sample sizes, one can construct conservative as well as exact confidence intervals. Extensions of the basic idea will allow us to predict other measures of diversity e.g. betadiversity and gammadiversity.
This research has been partially funded by the NIH grant 3R01GM04808013S1 and the NSF grant DMS0805950.
 Speaker: Louchard, Guy  Univ. Libre de Bruxelles, Belgium
 Title:Asymptotic independence of Uniform Markov chains

Abstract:
Let {X_{k}}_{k ≥ 0} be a discrete time Markov chain on the state space of positive integers. We assume that the chain is ergodic, and denote its stationary distribution by {π(j)}_{j > 0}. Let P(i,j), (i,j > 0), denote the transition probabilities. Our focus is on the chains that meet a uniformity condition: the series ∑_{j > 0}P(i,j) converges uniformly for i > 0. For the uniform chains, one should expect that, for a large j, the consecutive visits to D=[j,∞) occur at time moments far removed from each other. If so, the chain should have plenty of time to "stationarize" between the visits to D; specifically, for the repeat visits the distribution of a visited state should be close to {π(j)/π(D)}_{j ∈ D}, π(D): = ∑_{j ∈ D}π(j), and the interarrival times should be close to being independent, geometrically distributed with parameter π(D). Our goal is to fully confirm this longstanding conjecture.
This result will allow us to approximate the visit ("hitting") times and the visit ("hit") locations for such a remote D during a time interval [0,m] by an allocation model: at each step a ball lands in a box in D^{c} with probability π(D^{c}), and in a box j ∈ D with probability π(j)/π(D), independently of other balls. (Of course, for this to make sense, m→∞ and moreover π^{−1}(D)=O(m).)
Let us now see the evolution of the Markov process, for m steps, as an urn model, where we throw m balls into urns, (each visit to k throws a ball into urn k), and we are interested in random variables(RV) related to large j, as m→ ∞, for instance
 first empty urn
 last nonempty urn
 number of nonempty urns (measure of distinctness)
 number of urns with exactly i balls (i fixed)
 number of gaps, i.e. number of empty urns between urn 1 and the last nonempty urn
Assume that we can asymptotically use π(j) instead of P(i,j) i.e. we consider m iid RV with distribution π(j). It is known (by PoissonizationdePoissonization) that this is asymptotically equivalent to independent urns, where the number of balls in urn j is given by a Binomial B[mπ(j),mπ(j)(1−π(j))].
The motivation for this problem comes from the study of two Combinatorial structures: the columnconvex animals (cca) and the Carlitz compositions . These structures have been probabilistically analyzed in several previous papers with tools such that complex analysis, singularity analysis, hitting times analysis, Markov chains, moments of extremevalue related distributions functions. With the asymptotic independence property, we can now obtain, in an almost mechanical way, old and new results (old ones were usually derived by complicated machinery).
Joint work with Boris Pittel.
 Speaker: Mahmoud, Hosam  George Washington University
 Title:Gaussian phases in generalized coupon collection

Abstract:
A generalized coupon collection problem is considered in which a random number of purchases occurs at each stage of collecting n, a large number of coupons. We address the question of how many different coupons have been collected after k=k(n) draws, as n tends to infinity. We identify three phases of k(n): The sublinear, the linear, and the superlinear. In the sublinear phase we see o(n) different coupons, and with true randomness in the number of purchases, under the appropriate centering and scaling, a Gaussian distribution is obtained across the entire phase. However, if the number of purchases is fixed, a degeneracy comes into the picture and normality holds only at the higher end of this phase. In the case of a number of purchases with a fixed range, the small number of different coupons collected in the sublinear phase is upgraded to a number in need of centering and scaling to become normally distributed in the linear phase with a different normal distribution of the type that appears in the usual central limit theorems. The Gaussian results are obtained via martingale theory. We say a few words in passing about the high probability of collecting nearly all the coupons in the superlinear phase. It is our aim to present the results in a way to explore the critical transition at the "seam lines" between different Gaussian phases, and between these phases and other nonnormal phases.
 Speaker: Nebel, Markus  Univ. of Kaiserslautern, Germany
 Title:Maximum Likelihood Analysis of Algorithms

Abstract:
We present a new approach for an averagecases analysis of algorithms and data structures that supports a nonuniform distribution of the inputs and is based on the maximum likelihood training of stochastic grammars. The approach is exemplified by analyzing heapsort and quicksort comparing the results derived to known ones obtained by traditional techniques. Investigating traditional settings like the random permutation model we rediscover wellknown results formerly derived by pure analytic methods; changing to biased data yields original results which proves our method useful. All but one steps of our analysis can be automated on top of a computeralgebra system. Thus our new approach eases the effort required for an averagecase analysis exceptionally allowing for the consideration of realistic input distributions with unknown distribution functions at the same time.
As a byproduct our approach yields an easy way to generate random combinatorial objects according to various probability distributions.
 Speaker: Noy, Marc  Universitat Politècnica de Catalunya
 Title:Asymptotic properties of graphs of given genus

Abstract:
We show that the number of labelled graphs on n vertices embeddable in an orientable surface of genus g is asymptotically given by
c(g)n^{5(g−1)/2−1} γ^{n} n!, where c(g) is a constant depending on g and γ = 27.22688... is the exponential growth constant of planar graphs. We also show that several basic parameters, like number of edges, number of blocks, and size of the largest block, have a limit distribution law which does not depend on the genus. The proofs use the enumeration of maps on surfaces (Bender, Canfield, Richmond and others), the enumeration of labelled planar graphs (Giménez, Noy), and embeding results based on the facewidth parameter (Robertson, Vitray). Similar results hold for graphs embeddable in nonorientable surfaces.This is joint work with Guillaume Chapuy, Eric Fusy, Omer Giménez, and Bojan Mohar.
 Speaker: Roesler, Uwe  Univ. of Kiel, Germany
 Title:The Weighted Branching Process and Stochastic Fixed Points

Abstract:
We give a (personal) overview on the Weighted Branching Process and Fixed Point Equations, starting from the beginning to recent results and work in progress. Beside the mathematical aspect we present examples from various fields, like analysis of algorithms, population genetics, biology, financial mathematics and more.
 Speaker: Sankoff, David  Ottawa University, Canada
 Title:Gene order, gene clusters and random graphs

Abstract:
Comparisons of chromosomal gene order from different genomes may reveal various similarities. These may, however, be purely coincidental, especially in large genomes. We are thus motivated to study the chance similarities among random genomes as a baseline for testing the significance of the evolutionary relationship among real genomes. For example, definitions of conserved clusters in two genomes differ in how much emphasis they place on common gene content versus how similar are the orders of the common genes. We investigate the notion of generalized gene adjacency, a clustering criterion that adjusts the tradeoff between content and order. The connected components of the intersecting generalized adjacency graphs from two genomes become the gene clusters. These definintions require imposing values on some threshhold parameters. We suggest a way of determining "natural" values for the clustering parameters in terms of maximizing sensitivity of a weighting scheme on pairs of genes at different distances in two random genomes. This leads surprisingly to questions in the theory of record times of random variables. We also compare the percolation behaviour of the random adjacency graphs to other kinds of random graph.
 Speaker: Schaeffer, Gilles  LIX, Polytechnique, France
 Title:TBA

Abstract:
 Speaker: Soria, Michèle  LIP6/UPMC, France
 Title:Limiting Distribution for Distances in $k$trees and other graphs

Abstract:
This talk examines the distances between vertices in ktrees and other families of graphs. The starting point is a correspondence between these graphs and varieties of trees that can be specified in terms of combinatorial specifications. Distances in the graphs are transformed into parameters of trees that can be studed via generating functions and analytic combinatorics. For example, we show a Rayleigh limiting distribution for distances to a random vertex in a random ktree: in a ktree on n vertices, the proportion of vertices at distance d = x √n from a random vertex is asymptotic to (c_{k}^{2} x)/√n ×exp(−(c_{k}^{2} x^{2})/2), where c_{k}=k H_{k}.
Joint work with A. Darrasse and O. Bodini
 Speaker: Szpankowski, Wojciech  Purdue University, USA
 Title:On a nonprefix code and its analysis

Abstract:
In this talk, we discuss onetoone codes whose average length is smaller than the source entropy in defiance of the lower bound of Shannon. Onetoone codes are "one shot" codes that assign a distinct codeword to source symbols and are not necessarily prefix codes (more generally, uniquely decodable). First, we analyze a block code of length n generated for a binary memoryless source, and prove that the average redundancy is
−½ log_{2} n +C+F(n)+o(1), where C is a constant and either F(n)=0 if log_{2}(1−p)/p is irrational (p is the probability of generating a "0") or otherwise F(n) is a fluctuating function as the code length increases. Then we partially extend this result to nonbinary codes which turns out to be more interesting and analytically more challenging. These findings were derived by a combination of analytic tools such as precise evaluation of Bernoulli sums, the saddle point method, and theory of distribution of sequences modulo 1.
 Speaker: Vallée, Brigitte  CNRS, Caen, France
 Title:The number of symbol comparisons used by QuickSelect and by QuickSort

Abstract:
Philippe Flajolet (Overview), Brigitte Vallée (Averagecase analysis), and Jim Fill (Limiting distributions).
Consider n independent and identically distributed keys, each represented as an infinite string of symbols from a linearly ordered finite or countably infinite alphabet. Furthermore, assume that each time two keys are compared, they are compared symbolbysymbol until differing corresponding symbols are found. We analyze two algorithms: (i) QuickSort and (ii) QuickQuant(α), i.e., QuickSelect when it is used to find the αquantile. Let S_{n} be the total number of symbol comparisons used by the algorithm. Under a mild tamedness condition on how each key is generated probabilistically, we obtain two results: a precise asymptotic analysis of the mean number E[S_{n}] for both algorithms, and, in the case of QuickQuant(α), an explicit limiting distribution for S_{n} / n.
Jim Fill is currently working with Ph.D. student Patrick Bindjeme on a limiting distribution in the case of QuickSort.
 Speaker: van Leeuwaarden, Johan  Eindhoven Univ. of Technology and EURANDOM, Netherlands
 Title:Singularity analysis through functional equations for random walks in the quarter plane

Abstract:
We present a novel technique to derive asymptotic expressions for rare event probabilities for random walks in the quarter plane. For concreteness, we study a tandem queue with Poisson arrivals, exponential service times and coupled processors. The service rate for one queue is only a fraction of the global service rate when the other queue is non empty; when one queue is empty, the other queue has full service rate. The bivariate generating function of the queue lengths gives rise to a functional equation. In order to derive asymptotic expressions for large queue lengths, we combine the kernel method for functional equations with boundary value problems and singularity analysis. Joint work with Fabrice Guillemin (Orange).
 Speaker: Wilf, Herbert  Univ. of Pennsylvania, USA
 Title:Some new asymptotic problems in partition theory

Abstract:
Suppose the partitions of an integer n are restricted in the set of parts that can be used, and in the set of multiplicities of those parts. We'll speak about quantifying the influence of these restrictions on the asymptotic growth of the partition function, and will raise some unsolved problems.
For remarks and comments on these web pages, please contact Julien Clément.