Alois Panholzer

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 work: 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; and lastly, the largest connected component, for which we also observe a phase transition.

We consider a card guessing game with complete feedback. A ordered deck of n cards labeled 1 up to n is riffle-shuffled exactly one time. Then, the goal of the game is to maximize the number of correct guesses of the cards, where one after another a single card is drawn from the top, and shown to the guesser until no cards remain. Improving earlier results, we provide a limit law for the number of correct guesses. As a byproduct, we relate the number of correct guesses in this card guessing game to the number of correct guesses under a two-color card guessing game with complete feedback. Using this connection to two-color card guessing, we can also show a limiting distribution result for the first occurrence of a pure luck guess.

We consider the following card guessing game with no feedback. An ordered deck of n cards labeled 1 up to n is riffle-shuffled exactly one time. Then, the goal of the game is to maximize the number of correct guesses of the cards. One after another a single card is drawn from the top, the guesser makes a guess without seeing the card and gets no response if the guess was correct or not. Building upon and improving earlier results, we provide a limit law for the number of correct guesses and also show convergence of the integer moments.

This short note serves an addendum to the article "Destruction of very simple trees" by Fill, Kapur and Panholzer (2004). Therein, the limit law of one-sided tree destruction with a toll function was determined by its moment sequence. We add an identification of the limit law, using recent results of Bertoin (2022), in terms of the local time of a noise reinforced Bessel process.