Schedule for: 22w5004 - Analytic and Probabilistic Combinatorics

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

A brief introduction to BIRS with important logistical information, technology instruction, and opportunity for participants to ask questions.

We present a new algorithm for the cardinality estimation problem that is appropriate for practical applications. The algorithm can be implemented in a dozen lines of code and can accurately estimate the number of distinct elements in an input stream, using a very small amount of memory. The potential effectiveness of the algorithm is demonstrated by an approximate analysis and hypotheses about its performance that are validated through experiments using realistic inputs. An open problem in analytic combinatorics is a more precise analysis that can provide the more complete understanding of the algorithm that is needed to determine the effectiveness of variants and find effective parameter settings.

We obtain a concentration inequality for the maximum degree of a vertex in a uniformly random dissection of a polygon. This resolves a conjecture posed by Curien and Kortchemski in 2012. Our approach is based on a bijection with dual trees and the tools of analytic combinatorics. This is joint work with Douglas Rizzolo.

Two adjacent vertices in a rooted labelled tree are said to form an inversion if the parent has greater label than the child. We consider random rooted labelled trees for which the probability of a tree $T$ is proportionate to $q^{d(T)}$, where $d(T)$ is the number of descents and $q$ a positive real number. This random tree model interpolates between recursive trees ($q=0$) and uniformly random rooted labelled trees ($q=1$). Different structural aspects (local and global) of such random trees are investigated. The study of descent-weighted trees also leads naturally to the probabilistic study of permutations that are weighted in an analogous fashion.

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

Meet in the PDC front desk for a guided tour of The Banff Centre campus.

Meet in foyer of TCPL to participate in the BIRS group photo. The photograph will be taken outdoors, so dress appropriately for the weather. Please don't be late, or you might not be in the official group photo! For those joining virtually, please join us on zoom and turn your cameras on.

We extend the notion of classical parking functions by introducing randomness via a probabilistic parking protocol. We explore the properties of a preference vector given that it is a parking function and discuss the effect (and lack thereof) of the probabilistic parameter p. Of special interest is when p=1/2, where we demonstrate a sharp transition in some parking statistics. We connect our result to other phenomena in combinatorics and provide further directions for research. Partially based on joint work with Irfan Durmic, Alex Han, Pamela E. Harris, and Rodrigo Ribeiro.

A classic result by Frieze is that the total weight of the minimum spanning tree (MST) of the uniformly weighted graph converges to zeta(3). Recently, this result was extended to a uniformly weighted simplicial complex, where the role of the MST is played by its higher-dimensional analogue: the Minimum Spanning Acycle (MSA). In this talk, we look at the distribution of weights in this random MSA both in the bulk and in the extremes. We show that the rescaled empirical distribution of weights in the MSA converges to a measure based on the density of the shadow. We also show that the shifted extremal weights converge to an inhomogeneous Poisson point process. This is joint work with Sayan Mukherjee and Gugan Thoppe.

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

We prove that, for every $0 \leq t \leq 1$, the limiting distribution of the scale-normalized number of key comparisons used by the celebrated algorithm {\tt QuickQuant} to find the $t$th quantile in a randomly ordered list has a Lipschitz continuous density function $f_t$ that is bounded above by $10$. Furthermore, this density $f_t(x)$ is positive for every $x > \min\{t, 1 - t\}$ and, uniformly in $t$, enjoys superexponential decay in the right tail. We also prove that the survival function $1 - F_t(x) = \int_x^{\infty}\!f_t(y)\,\mathrm{d} y$ and the density function $f_t(x)$ both have the right tail asymptotics $\exp [-x \ln x - x \ln \ln x + O(x)]$. We use the right-tail asymptotics to bound large deviations for the scale-normalized number of key comparisons used by {\tt QuickQuant}. Our results also enable perfect simulation from the limiting distribution. This is joint work with Wei-Chun Hung.

Consider a collection (possibly infinite) of distinct containers in which balls are to be inserted. All containers have the same finite capacity r. Each arriving ball is to be placed in one of the containers, randomly (according to a given distribution) and independently of other balls. However, if the container selected for a given ball is already full, the ball lands in the overflow basket. We are interested in the number of balls in that basket as the number balls grows. The talk is based on joint work with R. Gouet and J. Wesolowski.

We will discuss a scaling limit for the sequence of generation sizes of a (rooted plane) tree with a given degree sequence. The main tools used in the proof include fluctuation theory and the stability analysis of a time-change equation for exchangeable increment processes. The scaling limit result extends and (probabilistically) proves a conjecture by Aldous concerning the profile of conditioned Galton-Watson trees first settled by Drmota and Gittenberger using analytic combinatorics.

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

We are going to describe some relatively simple instances when the notion of the Vapnik-Chervonenkis dimension leads to a variety of interesting questions in the study of finite point configurations in vector spaces over finite fields.

We will present a relation between weighted Catalan numbers and the phase transitions of a competitive growth process on a d-ary tree. The competitive growth processes presenting this relation are generalizations of chase-escape: chase-escape with death and distance-dependent chase-escape, which mimic the dynamics of a predator chasing prey, and the latter have random lifespans. This talk is based on joint works with Erin Beckman, Keisha Cook, Nicole Eikmeier, and Matthew Junge; and with Matthew Junge, Naina Ray and Nidhi Ray.

This talk covers how probabilistic analysis brought us to new insights in space-efficient tree data structures, and how an average-case lens on data structure problems yields challenging open problems for combinatorialists. More concretely, I will introduce a simple universal source code (compression method) for many random sources of binary or ordinal (a.k.a. plane) trees based on tree covering, a method invented for succinct tree data structures. 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 = Θ(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. The talk is mostly based on https://arxiv.org/abs/2104.13457

Motivated by the limit theory of combinatorial objects, specifically of word sequences, we consider a setting within which generalized versions of intensively studied problems can be stated, in particular, the Longest Common Subsequence problem, a problem about longest chains of randomly chosen points in 2D integer lattice, and the Longest Increasing Sequence problem. For the second of these problems we establish a precise relation between its classical and our proposed generalization. For the less understood first problem, we obtain similar results but modulo a conjecture concerning the natural analogue of the Chvátal-Sankoff constant for pairs of binary random words of given proportional length. Based on joint work with Hiệp Hàn (U. Santiago de Chile, Chile) and Matías Pavez Signé (U. of Warwick, UK)

The degree-restricted random process is a natural algorithmic model for generating graphs with degree sequence D_n=(d_1,...,d_n): starting with an empty n-vertex graph, it sequentially adds new random edges so that the degree of each vertex v_i remains at most d_i. It is natural to ask whether the final graph of this process is similar to a uniform random graph with degree sequence D_n (for d-regular degree sequences D_n this was already raised by Wormald in the mid 1990s). We show that, for degree sequences D_n that are not nearly regular, the final graph of the degree-restricted random process differs substantially from a uniform random graph with degree sequence D_n. Our proof uses the switching method, which is usually only applied to uniform random graph models -- rather than to stochastic processes. Based on joint work with Mike Molloy and Erlang Surya.

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

We consider generating functions such as those for restricted random walks, trees by size and type of node, statistical mechanical models, and so forth, defined implicitly by algebraic or transcendental equations. We give a means of analysis the depends only on the defining implicit equation and can typically be carried out in small computation times. These results give an alternative method to those of Greenwood et al. (Sem. Loth. Comb., 2022). The talk describes joint work in progress with Yuliy Baryshnikov.

Given a lattice L, we define a pop-stack sorting operator Pop that sends an element x to the meet of the elements covered by x. When L is the right weak order on the symmetric group, this operator acts by simply reversing the descending runs of a permutation. I will discuss several enumerative and analytic questions that emerge from studying the dynamical properties of Pop on specific lattices.

This talk surveys some recently developed software for analytic combinatorics, including a Sage package for the asymptotics of P-recursive sequences with explicit error terms (used for certifying sequence positivity), a Sage package for Analytic Combinatorics in Several Variables (ACSV) based on a symbolic-numeric algorithm and ball arithmetic, and a Julia package for ACSV that makes use of homotopy techniques for polynomial system solving. All software and source code is freely available on public repositories.

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

Random recursive trees and, more generally, weighted random recursive trees are rooted, labeled trees constructed by sequentially adding a new vertex, together with an associated weight, and connecting it to a previous vertex with probability proportional to its weight (the weights are iid and do not change throughout the process). Contrary to the qualitative behavior of linear preferential attachment trees where high-degree vertices become established from the early stages of the process, high-degree vertices in (weighted) random recursive trees keep changing throughout the process. We provide a description of both the order of the degree and the height of such high-degree vertices for (a wide class of weighted) random recursive trees and present some applications and open problems. This talk includes joint work with Bas Lodewijks and Marcel Ortgiese, and with Sergio López-Ortega and Marco López-Ortiz.

The continuum random tree is the scaling limit of the uniform spanning tree on the complete graph with $N$ vertices. The Aldous-Broder Markov chain on a graph $G=(V,E)$ is a Markov chain with values in the space of rooted trees whose vertex set is a subset of $V$ with the uniform distribution on the space of rooted trees spanning $G$. In Evans, Pitman and Winter (2006) the so-called root growth with regrafting process (RGRG) was constructed. Further it was shown that the suitable rescaled Aldous-Broder Markov chain converges to the RGRG weakly with respect to the Gromov-Hausdorff topology. It was shown in Peres and Revelle (2005) that (up to a dimension depending constant factor) the continuum random tree is with respect to the Gromov-weak topology the scaling limit of the uniform spanning tree on the torus $\mathbb{Z}_N^d$, $d\ge 5$. In the present talk we discuss that also the suitable rescaled Aldous-Broder Markov chain on $\mathbb{Z}_N^d$ for $d\ge 5$, converges to the RGRG weakly with respect to the Gromov-Hausdorff topology when initially started in the trivial rooted tree. The proof is mainly based in a combinatorial analysis of random walks on graphs.

The protection number of a vertex $v$ is the length of the shortest path from $v$ to any leaf contained in the maximal subtree where $v$ is the root. In this joint work with Clemens Heuberger and Stephan Wagner, we study the maximum protection number in simply generated trees using generating function and analytic techniques, and obtain the distribution for this parameter in general.

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

During the last 20 years various problems related to cutting trees have been studied by probabilistic or analytic combinatorics techniques. By extending the recursive approach, we reconsider some of such problems, as k-cutting of paths/trees, isolating multiple nodes in trees, and notions of records in trees, yielding old and adding some new results.

A long-standing problem proposed by David Aldous consists in giving a sharp upper bound for the mixing time of the so-called “triangulation walk”, a Markov chain defined on the set of all possible triangulations of the regular n-gon. A single step of the chain consists in performing a random edge flip, i.e. in choosing an (internal) edge of the triangulation uniformly at random and, with probability 1/2, replacing it with the other diagonal of the quadrilateral formed by the two triangles adjacent to the edge in question (with probability 1/2, the triangulation is left unchanged). While it has been shown that the relaxation time for the triangulation walk is polynomial in n and bounded below by a multiple of n^{3/2}, the conjectured sharpness of the lower bound remains firmly out of reach in spite of the apparent simplicity of the chain. For edge flip chains on different models -- such as planar maps, quadrangulations of the sphere, lattice triangulations and other geometric graphs -- even less is known. In this talk, I will discuss some relevant results and techniques developed in joint works with Alexandre Stauffer.

Groves are certain spanning forests of a subset of the triangular lattice that exhibit a limit shape phenomenon--a large random grove appears deterministic outside a region described by an algebraic curve. I will discuss how this algebraic curve can be computed using analytic combinatorics.

The continuous master theorem (CM) (Roura, 2001) is a powerful result which allows solving complex full history divide and conquer recurrences such as those arising in the analysis of quicksort, quickselect and various search trees with ease and without need of further sophisticated mathematical techniques. In this work we present two novel and interesting variants of K-dimensional trees, namely median and hybrid median K-d trees, and we carry out the analysis of their expected IPL (internal path length) and the expected cost of partial matches. For that, we use the CMT and the generalizations that we have developed to cope with linear systems of divide-and-conquer recurrences. WIthout these techniques at our disposal, the analysis would have been very likely a daunting or impossible task. The expected IPL of median and hybrid median is below 2n ln n + o(n log n) for any K>=2 and tends to the optimal n log_2 n + o(n log n) as K grows. The expected cost of partial match in median K-d trees is slightly worse than that for standard K-d trees, but the opposite is true for hybrid median K-d trees, and we conjecture that their exponent alpha approaches the optimal value 1-s/K as K grows, where s is the number of specified coordinates in the partial match. This is joint work with Amalia Duch, Mercè Pons and Salvador Roura.

We present an app that classifies musical scales with a thermodynamic search engine.

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

5-day workshop participants are welcome to use BIRS facilities (TCPL ) until 3 pm on Friday, although participants are still required to checkout of the guest rooms by 11AM.