Unfortunately drinks are not provided for this online conference. However, you are encouraged to bring your own drink and chat with members of the community. There will also be the possibility for checking technical details of the software used.

Session chair: Frédérique Bassino

Speaker affiliation: Laboratoire lorrain de Recherche en Informatique et ses Applications. Joint work with: Nicolas Auger, Cyril Nicaud and Carine Pivoteau (of which the initial part was presented at AofA2016 by Nicolas Auger)..

Abstract. In the average-case analysis of algorithms working on arrays of numbers (modeled by permutations), the uniform distribution on the set of possible inputs is usually assumed. However, the actual data on which these algorithms are used is rarely uniform, and often displays a bias towards 'sortedness'. In this talk, we present a non-uniform distribution on permutations, which favors their records (a.k.a. left-to-right maxima). We describe the average behavior of some classical permutation statistics in this model, some of which with applications to the analysis of algorithms. We also describe the 'typical shape' of permutations in our model, by means of their (deterministic) permuton limit.

Session chair: Frédérique Bassino

Speaker affiliation: Laboratoire d’Informatique Gaspard-Monge. Joint work with: Nicolas Auger, Cyril Nicaud, Carine Pivoteau, Ghazal Khalighinejad.

Abstract. Twenty years ago Timsort was invented, a surprisingly efficient sorting algorithm. One crucial aspect of Timsort is that it sorts presorted arrays (rare if array entries are elements of a large set chosen uniformly at random, but frequent in practice) in much fewer than the N log(N) operations that might be expected. We will present the algorithm and adequate measures of presortedness, explain why Timsort is so good on presorted data, and how one may still improve upon Timsort.

Session chair: Stephan Wagner

In order to simulate the real-life situation, if you would like to do the online equivalent of writing on the blackboard, you are welcome to share your screen or use the in-built blackboard of BigBlueButton.

Simulation of the lobby next to the lecture hall where people meet, have tea or coffee, check emails etc.

Session chair: Bruno Salvy

Speaker affiliation: University of Liverpool. Joint work with: J. Ian Munro, Patrick K. Nicholson, Louisa Seelbach Benkner.

Abstract. This talk covers some recent successes of taking an analysis-of-algorithms perspective in space-efficient data structures. More specifically, we show how tree covering, a method invented for succinct tree data structures, yields a simple universal source code for many random sources of binary or ordinal (a.k.a. plane) trees. Unlike other such codes, tree covering can be augmented to a data structure that supports a wide range of queries on the stored tree (without decompressing it first). I will present our analyses of subtree distributions and give some context about their applications in data structures and compression. Tree covering decomposes a (binary or ordinal a.k.a. plane) tree into $O(n/B)$ micro trees (connected subtrees) of $O(B)$ nodes each, with restricted connections between micro trees; our code uses $B=\Theta(\log n)$. While distributions of *fringe* subtrees are often well understood, the challenge in the analysis here is to bound the entropy of all micro-tree shape, including the non-fringe ones.

Session chair: Bruno Salvy

Speaker affiliation: Université Paris 13. Joint work with: Michael Engen.

Abstract. Given a permutation $\sigma$ of size $n$, a $k$-pattern of $\sigma$ is the permutation determined by any $k$ of its points. A permutation is $k$-optimal if it maximizes the number of different $k$-patterns it contains among all permutations of size $n$. In this talk, I will show algorithms to find these optimal permutations (with $n$ up to 18 using GPU programming).

Moderator: Michael Drmota

Don Knuth, Bob Sedgewick, Luc Devroye, and Wojciech Szpankowski, the four Philippe Flajolet Lecturers to date will be in a panel discussion about advances and directions of the area of “Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms” in the last decade, and how Philippe Flajolet’s monumental works still influence and shape the area ten years after his untimely death.

Session chair: Mihyun Kang

Speaker affiliation: Vienna University of Technology. Joint work with: Andrew Elvey Price, Wenjie Fang.

Abstract. The presence of a stretched exponential term $\mu^{n^{\sigma}}$ with $\mu>0$ and $\sigma \in (0,1)$ in a counting sequence $(c_n)_{n\geq0}$ is not common, although recently more and more examples emerge. It is generally quite difficult to prove that a sequence has a stretched exponential, which is partly due to the observation that such a sequence cannot be 'very nice': its generating function cannot be algebraic, and it can only be D-finite if it has an irregular singularity. Previously, the saddle point method was the only generic method for proving such a phenomenon, which, however, requires detailed information on the generating function. Recently, together with Andrew Elvey Price and Wenjie Fang, we have developed a new method on the level of recurrences to prove stretched exponentials. I will introduce the basics of this method and show how it can be extended to other problems. Then, I will summarize the recent progress (new bijections, limit laws, etc.) in the study of compacted trees, a subclass of directed acyclic graph. At the end, I will give an outlook how these results allow now an in-depth study of limit shapes and open many new avenues for further research.

Session chair: Mihyun Kang

Speaker affiliation: Wrocław University of Science and Technology. Joint work with: Bernhard Gittenberger, Isabella Larcher, Malgorzata Sulkowska.

Abstract. The number of embeddings of a partially ordered set S in a partially ordered set T is the number of subposets of T isomorphic to S. If both, S and T, have only one unique maximal element, we define good embeddings as those in which the maximal elements of S and T overlap. We investigate the number of good and all embeddings of a rooted poset S in the family of all binary trees on n elements considering two cases: plane (when the order of descendants matters) and non-plane. Furthermore, we study the number of embeddings of a rooted poset S in the family of all planted plane trees of size n. We derive the asymptotic behaviour of good and all embeddings in all cases and we prove that the ratio of good embeddings to all is of the order $\Theta(1/\sqrt{n})$ in all cases, where we provide the exact constants. Furthermore, we show that this ratio is non-decreasing with S in the plane binary case and asymptotically non-decreasing with S in the non-plane binary case and in the planted plane case. Finally, we comment on the case when S is disconnected.

Organizer: Benjamin Hackl

In this session, the presenters of the contributed videos will be available for questions and comments related to their work. After opening the session in the main BBB room, participants will be guided to a dedicated wonder.me space in which discussions can take place in (small) groups.

Simulation of the lobby next to the lecture hall where people meet, have tea or coffee, check emails etc.

Session chair: Cyril Banderier

Speaker affiliation: Stellenbosch University. Joint work with: H-K. Hwang, S. Wagner, V. Zacharovas.

Abstract. We consider the number of distinct parts in a random partition of $n$ into elements of a sequence of positive integers $\Lambda$. It is well known that if $\Lambda$ is the sequence of natural numbers, then the number of distinct parts in such a random partition is asymptotically normally distributed as $n\to\infty$. A similar result holds when the sequence $\Lambda$ satisfies the so-called Meinardus scheme, which is a set of strong analytic conditions on the Dirichlet series associated with the sequence $\Lambda$. Our aim is to prove asymptotic normality under weaker conditions. We will see in this talk that under a fairly mild growth condition on $\Lambda$, the variance tending to infinity is sufficient to guarantee asymptotic normality. Some important examples will also be discussed in this talk.

Session chair: Cyril Banderier

Speaker affiliation: The Polytechnic University of Catalonia. Joint work with: Marc Noy, Juanjo Rué.

Abstract. In the 1970s, Lovász and Plummer famously conjectured that a bridgeless cubic graph on n vertices has exponentially many perfect matchings. In 2011, it was finally proven by Esperet et al. that the number of perfect matchings is at least $2^{n/3656} \simeq 1.0002^n$. While in 2012, Chudnovsky and Seymour showed that if you restrict yourself to the special case of bridgeless cubic planar graphs, you get at least $2^{n/655978752} \simeq 1.000000001^n$ perfect matchings. In this talk, we will consider uniform random bridgeless cubic planar graphs with n labeled vertices. Under this model, we show that the expected number of perfect matchings is asymptotically $c\gamma^n$, where $c > 0$ and $\gamma \simeq 1.14196$ is an explicit algebraic number. We also compute it for (non necessarily bridgeless) cubic planar graphs and provide lower bounds for unlabeled graphs. Our starting point is a correspondence between counting perfect matchings in rooted cubic planar maps and the partition function of the Ising model in rooted triangulations.

Session chair: Cyril Banderier

Speaker affiliation: The University of British Columbia.

Abstract. The counting of paths on the square lattice is a standard way to introduce the mathematics of enumeration. One can vary these very basic problems by altering allowed steps, adding interactions, confining geometries and so on. These variations can quickly bring you to the cutting edge of mathematical research. The square lattice is, however, just one grid among many, and one can ask very similar questions about walks on different lattices. Group theory provides a huge number of possible replacements for the square lattice that bring all sorts of interesting questions. For an enumerator, there are 3 that stick out: Given an element of a group, how far is it from the identity element? Once we know how to compute distances, how many elements are at a given distance? Dual to that problem, how many words in the group start and end at the identity. I will talk about some of these problems and (hopefully) give some simple and not-so-simple examples, and discuss some open questions.

Session chair: Svante Janson

Speaker affiliation: The Johns Hopkins University.

Abstract. For general dimension $d$, we identify, with proof, the asymptotic conditional distribution of the number of (Pareto) records broken by an observation given that the observation sets a record. Fix $d$, and let ${\mathcal K}(d)$ be a random variable with this distribution. We show that the (right) tail of ${\mathcal K}(d)$ satisfies $\mathbb{P}({\mathcal K}(d) \geq k) \leq \exp\left[ - \Omega\!\left( k^{(d - 1) / (d^2 - 2)} \right) \right]$ as $k \to \infty$ and $\mathbb{P}({\mathcal K}(d) \geq k) \geq \exp\left[ - O\!\left( k^{1 / (d - 1)} \right) \right]$ as $k \to \infty$. When $d = 2$, the description of ${\mathcal K}(2)$ in terms of a Poisson process agrees with the main result from Fill [*Comb. Probab. Comput.* 30 (2021) 105--123] that the distribution of ${\mathcal K}(2)$ is Geometric$(1/2)$ with support $\{0, 1, \ldots\}$. We show that $\mathbb{P}({\mathcal K}(d) \geq 1) = \exp[-\Theta(d)]$ as $d \to \infty$; in particular, ${\mathcal K}(d) \to 0$ in probability as $d \to \infty$.

Session chair: Svante Janson

Speaker affiliation: University of Bath. Joint work with: Markus Heydenreich, Alex Drewitz.

Abstract. Take k nodes uniformly at random in a n-node graph, and let k competing epidemics spread along edges at constant speed from these initial nodes, infecting nodes when they reach them. A node can only get infected by one of the epidemics, the first one that reaches it. We are interested in the sizes of the final territories of the k epidemics, which we call the Voronoi cells of the k initial nodes. In this joint work with Markus Heydenreich (Munich) and Alex Drewitz (Cologne), we prove limiting theorems for the sizes of the Voronoi cells of k nodes taken uniformly at random in an n-node random split tree.

Simulation of the lobby next to the lecture hall where people meet, have tea or coffee, check emails etc.

Session chair: Nicolas Broutin

Speaker affiliation: Duke Kunshan University. Joint work with: Pietro Caputo, Guillem Perarnau, Matteo Quattropani.

Abstract. In this talk we will consider the extremal values of the stationary distribution of the sparse directed configuration model. Under the assumption of linear $(2+\eta)$-moments on the in-degrees and of bounded out-degrees, we obtain tight comparisons between the maximum value of the stationary distribution and the maximum in-degree. Under the further assumption that the order statistics of the in-degrees have power-law behavior, we show that the upper tail of the stationary distribution also has power-law behavior with the same index. Moreover, these results extend to the PageRank scores of the model, thus confirming a version of the so-called power-law hypothesis.

Session chair: Nicolas Broutin

Speaker affiliation: Princeton University.

Abstract. We compare several methodologies to either compute or approximate the enumeration of a combinatorial class: 1. The 'compact encoding' methodology, in which an encoding of the objects of the combinatorial class is designed, and then the enumeration sequence is bounded by lower/upper-bounding the number of bits required by the encoding for any object of a given size. 2. A method using the analytic combinatorics toolset, in which a bijection allows us to reduce the objects of the combinatorial class to an easier to count class, which can then be exactly enumerated using existing techniques. 3. A 'hybrid' methodology, in which we design an encoding for the combinatorial class, but then count all possible encodings using analytic combinatorics tree enumeration techniques. We argue that the third method provides a good trade-off between technical complexity and accuracy. We illustrate these arguments on various examples taken from recent work on the enumeration of unlabeled graph classes, including papers by Nakano et al., Lumbroso and Shi, and Chauve et al..

Session chair: Nicolas Broutin

Speaker affiliation: Université de Tours. Joint work with: Colin Defant, Anthony J. Guttmann.

Abstract. In his seminal book, ``the art of computer programming'', Knuth discussed the enumeration of permutations which can be sorted by a single stack. West later defined the stack-sorting map in a deterministic way, such that repeatedly applying this map to a permutation of length $n$ results in the identity permutation after at most $n-1$ steps. The number of permutations that are sorted by $k$ applications of this map is known only for $k\leq2$. I will discuss recent work on the case $k=3$, in particular I will describe an algorithm we applied to enumerate these permutations up to length $n=1000$ and our subsequent analysis of these numbers.

Chef: Daniel Krenn

This includes an online cooking session (in BBB) where you can learn how to prepare the Carinthian traditional dish “Kasnudeln”. There is no obligation to cook; just stop by to socialise and/or eat your own food.

Recipe for “Kärntner Kasnudeln”

The following recipe for “Kärntner Kasnudeln” is for 2 portions.

Note (Efficient Preparation). The most time-consuming part is boiling the potatoes, so start this first (or even before the actual cooking session starts).

Dough

For the dough, mix the following ingredients:

• 250g flour
• 1/2 tsp. salt
• 1 small egg (skip for vegan)
• 1 tbsp. oil
• some water (see below)

Add small amounts of the water until it becomes a moderately firm dough.

Filling

For the filling, mix the following ingredients:

• 100g potatoes (peeled, boiled and mashed)
• 40g onion + 1 tbsp. butter (onion finely cut and fried in butter)
• 1 tbsp. parsley (finely cut)
• 1 tbsp. mint (finely cut)
• 1 tbsp. chervil (finely cut)
• 250g cottage cheese (see note below)

Note (Spices). You may experiment with the spicing and replace it by spices you like.

Note (Mint). The traditional kind of mint used for Kasnudel is Kärntner Nudelminze (Mentha austriaca, Mentha x carinthiaca). It is said that this mint tastes slightly sweet. However, you can use any kind of mint you can get your hands on.

Note (Cottage Cheese). The cottage cheese used for Kasnudel is traditionally Kärntner Bröseltopfen. Unfortunately, it seems to be available only regionally in the province Carinthia of Austria. Within Austria, the usual Topfen (German: Quark) can be used as an alternative. A list of alternatives that will work well:

• Topfen (or Quark)
• any kind of cream cheese (like Philadelphia)
• any kind of vegan cream cheese like product
• Fromage blanc (probably works; untested)

Note (Vegan Option). As mentioned above, you can use any kind of vegan cream cheese like product instead of the cottage cheese. You can also simply replace butter by some vegan margarine, use olive oil or any other kind of oil you like.

“Krendeln”

The process of merging the filling and the dough (“krendeln”) will be explained during the cooking session.

Steaming or Boiling

Either

• Boil 12 minutes in salted, boiling water, or
• heat in steam for 20 minutes.

Finishing and Extras

There are several options how to serve Kasnudel:

1. Before serving add melted butter (60g) on top of the Kasnudeln.
2. Fry the boiled Kasnudel in butter (or oil) before serving. This option is often used for eating left-over Kasnudel on the next day.

There are some extras you can put on the Kasnudel:

• chives (finely cut)
• Grammeln (crispy-roasted small pieces of bacon; see also cracklings)

Session chair: Ralph Neininger

Speaker affiliation: University of Melbourne. Joint work with: Andrew Barbour, Graham Brightwell.

Abstract. We present new concentration inequalities for Markov chains (in discrete and continuous time), generalising results for chains that are contracting in Wasserstein distance. We further extend the notion of cut-off to chains with infinite state space. We illustrate our results with examples.

Session chair: Ralph Neininger

Speaker affiliation: Uppsala University. Joint work with: Laura Eslava, Sarah Penington.

Abstract. We define a graph process based on a discrete branching process with deletions and mergers, which is inspired by the 4-cycle structure of both the hypercube $\mathcal{Q}_d$ and the lattice $\mathbb{Z}^d$ for large $d$. We prove survival and extinction under certain conditions on $p$ and $q$ that heuristically match the known expansions of the critical probabilities for bond percolation on these graphs.

Simulation of the lobby next to the lecture hall where people meet, have tea or coffee, check emails etc.

Session chair: Hosam Mahmoud

Speaker affiliation: Munich University.

Abstract. Corroborating a prediction from statistical physics, we prove that the Belief Propagation message passing algorithm approximates the partition function of the random k-SAT model well for all clause/variable densities and all inverse temperatures for which a modest absence of long-range correlations condition is satisfied. This condition is known as 'replica symmetry' in physics language. From this result we deduce that a replica symmetry breaking phase transition occurs in the random k-SAT model at low temperature for clause/variable densities below but close to the satisfiability threshold.

Session chair: Hosam Mahmoud

Speaker affiliation: Uppsala University. Joint work with: Gabriel Berzunza.

Abstract. We consider the model of random trees introduced by Devroye (1998), the so-called random split trees. The model encompasses many important randomized algorithms and data structures. We then perform supercritical Bernoulli bond-percolation on those trees and obtain the asymptotic distribution for the sizes of the largest clusters.

Session chair: Hosam Mahmoud

Speaker affiliation: Vienna University of Technology. Joint work with: K. Panagiotou, L. Ramzews.

Abstract. Devising and implementing samplers for random discrete structures helps us to understand their shape, make new observations, and verify theoretical results. The widely used Boltzmann sampler framework constructs such samplers by translating combinatorial decompositions of structures into randomized algorithms. Typically, such procedures perform approximate size sampling in linear time, but exact-size sampling only in quadratic time. This talk about joint work with K. Panagiotou and L. Ramzews describes how to achieve linear time exact-size sampling and outperform state of the art Boltzmann samplers in a general setting. We provide applications to a variety of classes of graphs, permutations, and phylogenetic networks.

Session chair: Bruno Salvy

AofA2021 Business Meeting.