Session chair: Mark Daniel Ward

Speaker affiliation: Purdue University.

Abstract. "Philippe always enjoyed our effort to extend analytic combinatorics to information theory. In this talk we first briefly review some results obtained in analytic information theory that led to very precise asymptotics of the minimax redundancy for universal source coding. Then we go beyond this trodden path and attempt to apply analytic tools to some machine learning problems. In particular, we present some new results on regret for online regression with logarithmic loss."

coffee to be served near DRL room A8

Session chair: Mark Daniel Ward

Abstract. We study the size of the automorphism group of two different types of random trees: Galton-Watson trees and Pólya trees. In both cases, we prove that it asymptotically follows a log-normal distribution. While the proof for Galton-Watson trees mainly relies on probabilistic arguments and a general result on additive tree functionals, generating functions are used in the case of Pólya trees.

Session chair: Mark Daniel Ward

Abstract. We consider the process of uncovering the vertices of a random labeled tree according to their labels. First, a labeled tree with $n$ vertices is generated uniformly at random. Thereafter, the vertices are uncovered one by one, in order of their labels. With each new vertex, all edges to previously uncovered vertices are uncovered as well. In this way, one obtains a growing sequence of forests. Three particular aspects of this process are studied in this extended abstract: first the number of edges, which we prove to converge to a stochastic process akin to a Brownian bridge after appropriate rescaling. Second, the connected component of a fixed vertex, for which different phases are identified and limiting distributions determined in each phase. Lastly, the largest connected component, for which we also observe a phase transition.

on one's own

Session chair: Brigitte Vallée

Speaker affiliation: Uppsala University. Joint work with: Jim Fill.

Abstract. "Philippe Flajolet had many talents, but he is perhaps best known for his contributions to Analytic Combinatorics using generating functions as a central tool. I, on the other hand, have mostly used other, more probabilistic tools. These different methods should not be seen as enemies, but as friendly complements, that both can help us solve problems that we are interested in. I will illustrate this by talking about some recent (and some not so recent) results on sums of powers of subtree sizes for random trees, in particular conditioned Galton-Watson trees; for this problem, we use both methods: probabilistic methods to prove some results, and generating functions to prove some others. Mainly based on [arXiv:2104.02715](https://arxiv.org/abs/2104.02715) (joint work with Jim Fill)."

Session chair: Brigitte Vallée

Abstract. We propose a modification to the random destruction of graphs: Given a finite network with a distinguished set of sources and targets, remove (cut) vertices at random, discarding components that do not contain a source node. We investigate the number of cuts required until all targets are removed, and the size of the remaining graph. This model interpolates between the random cutting model going back to Meir and Moon \cite{MeirMoon1970} and site percolation. We prove several general results, including that the size of the remaining graph is a tight family of random variables for compatible sequences of expander-type graphs, and determine limiting distributions complete binary trees.

Session chair: Brigitte Vallée

Abstract. We are interested in the independence number of large random symply generated trees and related parameters, such as their matching number or the kernel dimension of their adjacency matrix. We express these quantities using a canonical tricolouration, which is a way to colour the vertices of a tree with three colours. As an application we obtain limit theorems in $L^p$ for the renormalised independence number in large simply generated trees (including large size-conditioned Bienaymé-Galton-Watson trees).

These two restaurants are about 1 block away from each other in South Philly. Pat's is located at 1237 E Passyunk Ave, and Gino's is located nearby at 1219 S 9th St. Everywhere else in the USA, there is a sandwich called Philly Cheesesteak, but in Philly, these are just called Cheesesteak. It is one of the most iconic foods from Philadelphia.

Session chair: Frédérique Bassino

Speaker affiliation: Université de Bordeaux.

Abstract. "The study of lattice walks confined to cones is a lively topic in enumerative combinatorics, and has witnessed rich developments in the past 20 years. Typically, one is given a finite set of steps $S$ in $Z^d$, and a cone $C$ in $R^d$. Exactly $|S|^n$ walks of length $n$ start from the origin and take their steps in $S$. But how many remain in the cone $C$? One of the motivations for studying such questions is that such walks encode many objects in discrete mathematics, computer science, probability theory, among other fields. In the past 20 years, several approaches have been combined to understand how the choice of the steps and of the cone influence the nature of the counting sequence $a(n)$, or of the the associated series $A(t)=\sum a(n) t^n$. Is $A(t)$ rational, algebraic, or solution of a differential equation? Here we will focus on cases where $A(t)$ is algebraic, and explain how this can be derived using "invariants", a tool invented by William Tutte in his study of coloured planar triangulations.

coffee to be served near DRL room A8

Session chair: Frédérique Bassino

Abstract. Catalytic equations appear in several combinatorial applications, most notably in the enumeration of lattice paths and in the enumeration of planar maps. The main purpose of this paper is to show that under certain positivity assumptions the dominant singularity of the solution function has a universal behavior. We have to distinguish between linear catalytic equations, where a dominating square-root singularity appears, and non-linear catalytic equations, where we -- usually -- have a singularity of type $3/2$.

Session chair: Frédérique Bassino

Abstract. The University of Pennsylvania has a fire drill scheduled during this time. The conference organizers apologize for this brief interruption in the schedule. We will take advantage of this time to walk five minutes west of DRL and take a picture near the statue of Benjamin Franklin in Blanche P. Levy Park.

Session chair: Frédérique Bassino

Abstract. Tree-child networks are one of the most prominent network classes for modeling evolutionary processes which contain reticulation events. Several recent studies have addressed counting questions for bicombining tree-child networks which are tree-child networks with every reticulation node having exactly two parents. In this paper, we extend these studies to d-combining tree-child networks where every reticulation node has now d parents. Moreover, we also give results and conjectures on the distributional behavior of the number of reticulation nodes of a network which is drawn uniformly at random from the set of all tree-child networks with the same number of leaves.

on one's own

Session chair: Bruno Salvy

Speaker affiliation: Université de Caen. Joint work with: Ali Akhavi and Frédéric Paccaut.

Abstract. "Most of the natural sources that intervene in Information Theory have a positive entropy. They are well studied. The paper aims in building, in an explicit way, natural instances of sources with zero entropy. Such instances are obtained by slowing down sources of positive entropy, with processes which rescale sources or insert delays. These two processes --rescaling or inserting delays-- are essentially the same; they do not change the fundamental intervals of the source, but only the ``depth'' at which they will be used, or the ``speed'' at which they are divided. However, they modify the entropy and lead to sources with zero entropy. The paper begins with a ``starting'' source of positive entropy, and uses a natural class of rescalings of sublinear type. In this way, it builds a class of sources of zero entropy that will be further analysed. As the starting sources possess well understood probabilistic properties, and as the process of rescaling does not change its fundamental intervals, the new sources keep the memory of some important probabilistic features of the initial source. Thus, these new sources may be thoroughly analysed, and their main probabilistic properties precisely described. We focus in particular on two important questions: exhibiting asymptotical normal behaviours à la Shannon-MacMillan-Breiman; analysing the depth of the tries built on the sources. In each case, we obtain a parameterized class of precise behaviours. The paper deals with the analytic combinatorics methodology and makes a great use of generating series."

Session chair: Bruno Salvy

Abstract. We study the asymptotic behaviour of random integer partitions under a new probability law that we introduce, the Plancherel–Hurwitz measure. This distribution, which has a natural definition in terms of Young tableaux, is a deformation of the classical Plancherel measure. It appears naturally in the enumeration of Hurwitz maps, or equivalently transposition factorisations in symmetric groups. We study a regime in which the number of factors in the underlying factorisations grows linearly with the order of the group, and the corresponding maps are of high genus. We prove that the limiting behaviour exhibits a new, twofold, phenomenon: the first part becomes very large, while the rest of the partition has the standard Vershik–Kerov–Logan–Shepp limit shape. As a consequence, we obtain asymptotic estimates for unconnected Hurwitz numbers with linear Euler characteristic, which we use to study random Hurwitz maps in this regime. This result can also be interpreted as the return probability of the transposition random walk on the symmetric group after linearly many steps.

Session chair: Bruno Salvy

Abstract. In this article, a novel method to compute all discrete polyharmonic functions in the quarter plane for models with small steps, zero drift and a finite group is proposed. A similar method is then introduced for continuous polyharmonic functions, and convergence between the discrete and continuous cases is shown.

NA

Located at 121 N. Columbus Blvd. at Cherry Street Pier, it provides a beautiful view of the Delaware River. There are many options for drinks. On Tuesdays, they have Tacos for only two dollars.

Session chair: Michael Drmota

Speaker affiliation: Technical University of Denmark.

Abstract. In this talk we will study tries in the pointer machine model. We will first introduce the top tree compression scheme, which is a compression scheme for labeled trees based on top trees. Then we will see how top tree compression can be used to store a trie in o(n) space while obtaining optimal query time. Along the way we develop several interesting data structures that work on a pointer machine. These include an optimal data structure for random access to a grammar-compressed string and an optimal data structure for a variant of the level ancestor problem.

coffee to be served near DRL room A8

Session chair: Michael Drmota

Abstract. We present the analysis of the depth first search algorithm in random digraph model with geometric degree distributions. This problem posed by Don Knuth in his next to appear volume of The Art of Computer Programming gives interesting insight in one of the most elegant and efficient algorithm for graph analysis due to Tarjan.

Session chair: Michael Drmota

Abstract. For a positive integer $n$ and a real number $p\in (0, 1)$, a random directed acyclic digraph $\mathbb{D}_{ac}(n,p)$ is obtained from the binomial random directed $\mathbb{D}(n,p)$ conditioned to be acyclic, i.e., directed cycles are forbidden. Here, by the binomial model $\mathbb{D}(n,p)$ we mean the random digraph where every possible directed edge (excluding loops) occurs independently with probability $p$. Sources and sinks are among the most natural characteristics of directed acyclic graphs. For example, it is a well known fact that a non-empty directed acyclic graph must have at least one source and one sink. We investigate the distribution of the number of sources in $\mathbb{D}_{ac}(n,p)$ when $p$ is of the form $\lambda/n$, where $\lambda$ is a fixed positive constant. Because of symmetry, the number of sinks will have the same distribution as the number of sources. Our main motivation is to understand how this distribution changes as we pass through the critical point $p=1/n$. Since we are in the sparse regime, it makes sense to include the number of isolated vertices as well. In a directed graph an isolated vertex can be regarded as a vertex that is both a source and a sink. We prove asymptotic normality for each of these parameters when $p=\lambda/n$. Our method is based on the analysis of a multivariate generating function from a work of Gessel.

on one's own

Session chair: Hosam Mahmoud

Abstract. Recursive sequences of laws of random variables (and random vectors) are considered where an independence assumption which is usually made within the setting of the contraction method is dropped. This restricts the study to sequences which after normalization lead to asymptotic normality. We provide a general univariate central limit theorem which can directly be applied to problems from the analysis of algorithms and random recursive structures without further knowledge of the contraction method. Also multivariate central limit theorems are shown and bounds on rates of convergence are provided. Examples include some previously shown central limit analogues as well as new applications on Fibonacci matchings.

Session chair: Hosam Mahmoud

Abstract. We continue the investigation, that was begun by Aldous, Evans and Pitman (1998), and study the fragmentation process obtained by deleting randomly chosen edges from a critical Galton-Watson tree $\mathbf{t}_{n}$ conditioned on having $n$ vertices, whose offspring distribution belongs to the domain of attraction of a stable law of index $\alpha \in (1,2]$. Our main result establishes that, after rescaling, the fragmentation process of $\mathbf{t}_{n}$ converges as $n \rightarrow \infty$ to the fragmentation process obtained by cutting-down proportional to the length on the skeleton of an $\alpha$-stable Lévy tree of index $\alpha \in (1,2]$. We further establish that the latter can be constructed by considering the partitions of the unit interval induced by the normalized $\alpha$-stable Lévy excursion with a deterministic drift studied by Miermont (2001). In particular, this extends the result of Bertoin (2000) on the fragmentation process of the Brownian CRT.

Philadelphia has a long history of brewing. Wednesday evenings provide an excellent way to explore the city's brews. Center City District SIPS "Beginning June 1, participating locations will offer 6 dollar cocktails, 5 dollar wine, 4 dollar beer and half-priced appetizers every Wednesday from 4:30 - 7 p.m."

Session chair: Bob Sedgewick

Speaker affiliation: École polytechnique. Joint work with: Laurent Ménard and Gilles Schaeffer.

Abstract. "A planar map is an embedding of a planar graph in the sphere, considered up to deformations. A triangulation is a planar map, where all the faces are triangles. In 2003, in order to define a model of generic planar geometry, Angel and Schramm studied the limit of random triangulations on the sphere. They proved that this model of random maps converges for the Benjamini-Schramm topology, or local topology, towards the now famous Uniform Infinite Planar Triangulation (or UIPT), a probability distribution on infinite triangulations. Soon after, Angel studied some properties of the UIPT. He established that the volume of the balls the UIPT of radius R scales as R^4. Similar results (but with quite different proofs) were then obtained for quadrangulations by Chassaing and Durhuus and Krikun. The results cited above deal with models of maps that fall in the same ``universality class'', identified in the physics literature as the class of ``pure 2D quantum gravity'': the generating series all admit the same critical exponent and the volume of the balls of the local limits of several of those models of random maps are known to grow as R^4.To capture this universal behaviour, a good framework is to consider scaling limits of random maps in the Gromov Hausdorff topology. Indeed, for a wide variety of models the scaling limit exists and is the so-called Brownian sphere, as initially established by Miermont and Le Gall. To escape this pure gravity behaviour, physicists have long ago understood that one should ``couple gravity with matter'', that is, consider models of random maps endowed with a statistical physics model. I will present in particular the case of triangulations decorated by an Ising model. It consists in colouring in black and white the vertices of a triangulation, and consider probability distribution which are now biased by their number of monochromatic edges. In a recent work, in collaboration with Laurent Ménard and Gilles Schaeffer, we proved that the local limit of this model also exists. In this talk, I will try to present these results in the most self-contained way as possible and explain the main ideas underlying their proof."

coffee to be served near DRL room A8

Session chair: Bob Sedgewick

Abstract. Affirmative Sampling is a practical and efficient novel algorithm to obtain random samples of distinct elements from a data stream. Its most salient feature is that the size S of the sample will, on expectation, grow with the (unknown) number n of distinct elements in the data stream. As any distinct element has the same probability to be sampled, and the sample size is greater when the ``diversity'' (the number of distinct elements) is greater, the samples that Affirmative Sampling delivers are more representative than those produced by any scheme where the sample size is fixed a prori---hence its name.

Session chair: Bob Sedgewick

Abstract. Quad-K-d trees (Bereckzy et al. (2014)) are a generalization of several well-known hierarchical K-dimensional data structures. They were introduced to provide a unified framework for the analysis of associative queries and to investigate the trade-offs between the cost of different operations and the memory needs (each node of a quad-K-d tree has arity 2^m for some m, 1 <= m <= K). Indeed, we consider here partial match --one of the fundamental associative queries-- for several families of quad-K-d trees including, among others, relaxed K-d trees and quadtrees. In particular, we prove that the expected cost of a random partial match P'_n that has s out of K specified coordinates in a random quad-K-d tree of size n is \beta n^\alpha + l.o.t where \alpha and \beta are constants given in terms of K and s as well as additional parameters that characterize the specific family of quad-K-d trees under consideration. Additionally, we derive a precise asymptotic estimate for the main order term of P_{n,q} --the expected cost of a fixed partial match in a random quad-K-d tree of size n. The techniques and procedures used to derive the mentioned costs extend those already successfully applied to derive analogous results in quadtrees and relaxed K-d trees; our results show that the previous results are just particular cases, and extends the validity of the conjecture made in (Duch et al. (2016)) to a wider variety of multidimensional data structures.

on one's own

Session chair: Michael Fuchs

Speaker affiliation: University of Chile.

Abstract. "The state of the art in database query processing has recently been shaken by a new generation of multi-join processing algorithms with strong optimality guarantees based on the AGM bound of queries: the maximum size of the output of the query over all possible relations with the same cardinalities. Over the years, this has been shown to translate into considerable practical improvements over the classical binary join techniques in use since the sixties. In this talk I will first present the AGM bound, which is quite interesting from an analysis-of-algorithms perspective (even if worst-case). I will then show how it has been typically achieved by following its formula, which has led to the well-known Leapfrog TrieJoin algorithm. Finally, I will introduce a new data structure that regards d-column tables as points in a d-dimensional space and represents those grids using, essentially, d-dimensional versions of quadtrees. The join algorithm is then implemented by (virtually) raising their dimension to include the missing attributes of the join, and then (virtually) traversing their intersection, or equivalently the output space. I will then show how this extremely simple geometric approach does reach worst-case-optimality in a completely different way. This talk is based on our work "Optimal Joins using Compressed Quadtrees", which is to appear in ACM Transactions on Database Systems."

Session chair: Michael Fuchs

Abstract. Given a positive-integer-valued vector $u=(u_1,\ldots,u_m)$ with $u_1 < \ldots < u_m$. A u-parking function of length m is a sequence $\pi=(\pi_1,...,\pi_m)$ of positive integers whose non-decreasing rearrangement $(\lambda_1,...,\lambda_m)$ satisfies $\lambda_i\leq u_i$ for all $1\leq i\leq m$. We introduce a combinatorial construction termed a parking function multi-shuffle to generic u-parking functions and obtain an explicit characterization of multiple parking coordinates. As an application, we derive various asymptotic probabilistic properties of a uniform u-parking function when $u_i=cm+ib$. The asymptotic scenario in the generic situation $c>0$ is in sharp contrast with that of the special situation $c=0$.

Session chair: Bruno Salvy

AofA2022 Business Meeting.

(taking some quotations from their website) Han Dynasty opened its doors in 2007 as a Mother-Son restaurant bringing Sichuan style spice to the American audience. They are committed to sharing the authentic cuisine of the Sichuan Chinese culture and the tradition behind it. Han Dynasty is located at 3711 Market Street in University City. There is a large building at 3711 Market Street, and the restaurant is on the street level. When you walk there, it will be the third door at street level. Inside the restaurant is very loud, and it should not rain this evening, so we decided to sit outside. The atmosphere is not fancy, but the food should be amazing. We will have a tasting, in which many rounds of foods are available at the table, for everybody to share, in a family style. The cost of the meal is free. All costs for the conference dinner will be covered by the conference organizer.

Session chair: Michael Wallner

Speaker affiliation: University of Leicester.

Abstract. In recent years, there has been an explosion of interest in succinct data structures, which store the given data in compact or compressed formats and answer queries on the data rapidly while it is still in its compressed format. Many compressed data structures rely upon explicit formulas for counting combinatorial objects in order to determine their space usage. Perhaps the purest expression of this is in so-called /encoding/ data structures, a special kind of succinct data structure. Our focus in this talk is to introduce succinct data structures (and encoding data structures) and their relation to counting problems.

coffee to be served near DRL room A8

Session chair: Michael Wallner

Abstract. A polynomial is called self-reciprocal (or palindromic) if the sequence of its coefficients is palindromic. In this paper we obtain improved error bounds for the number of irreducible polynomials and self-reciprocal irreducible monic polynomials with prescribed coefficients over a finite field. The improved bounds imply self-reciprocal irreducible monic polynomials with degree $2d$ and prescribed $\ell$ leading coefficients always exist provided that $\ell$ is slightly less than $d/2$.

Session chair: Michael Wallner

Abstract. The paper deals with a load-balancing algorithm for a closed stochastic network with two zones with different demands. The algorithm is motivated by an incentive algorithm for redistribution of cars in a large-scale car-sharing system. The service area is divided into two zones. When cars stay too much long in the low-demand zone, users are encouraged to pick up them and return them in the high-demand zone. The zones are divided in cells called stations. The cars are the network customers. The mean-field limit solution of an ODE gives the large scale distribution of the station state in both clusters for this incentive policy in a discrete Markovian framework. An equilibrium point of this ODE is characterized via the invariant measure of a random walk in the quarter-plane. The proportion of empty and saturated stations measures how the system is balanced. Numerical experiments illustrate the impact of the incentive policy. Our study shows that the incentive policy helps when the high-demand zone observes a lack of cars but a saturation must be prevented especially when the high-demand zone is small.

Public market that has been in Philadelphia since 1893. There are a wide variety of foods to choose from.

Built to celebrate the United States Centennial (1876), this is one of the most famous art galleries in the USA.

King of Prussia has the 3rd largest mall in the United States, with more than 450 stores. King of Prussia's mall offers tax free purchases on clothes and shoes.

The events for Friday include Festival of Fountains, Open Air Theatre Fountain Shows, Main Fountain Garden Performances, Behind the Scenes Tour of Under the Fountains, Live Music in the Beer Garden, and Illuminated Fountain Performances. See the listing of the events.