We introduce the problem of isolating several nodes in random recursive trees by successively removing random edges, and study the number of random cuts that are necessary for the isolation. In particular, we analyze the number of random cuts required to isolate $\ell$ selected nodes in a size-$n$ random recursive tree for three different selection rules, namely (i) isolating all of the nodes labelled $1,2,\dots ,\ell$ (thus nodes located close to the root of the tree), (ii) isolating all of the nodes labelled $n+1–\ell ,n+2–\ell ,\dots ,n$ (thus nodes located at the fringe of the tree), and (iii) isolating $\ell$ nodes in the tree, which are selected at random before starting the edge-removal procedure. Using a generating functions approach we determine for these selection rules the limiting distribution behaviour of the number of cuts to isolate all selected nodes, for $\ell$ fixed and $n\to \mathrm{\infty }$.

Guibert and Linusson introduced the family of doubly alternating Baxter permutations, i.e., Baxter permutations $\sigma \in S_n$, such that $\sigma$ and ${\sigma }^{-1}$ are alternating. They proved that the number of such permutations in $S_{2n}$ and $S_{2n+1}$ is the Catalan number $C_n$. In this paper, we compute the expected limit shape of such permutations, following the approach by Miner and Pak.

In his celebrated proof of Szemerédi’s theorem that a set of integers of positive density contains arbitrarily long arithmetic progressions, W. T. Gowers introduced a certain sequence of norms $\parallel \cdot {\parallel }_{U^2[\mathbb{N}]}\le \parallel \cdot {\parallel }_{U^3[\mathbb{N}]}\le \cdots$ on the space of complex-valued functions on the set $[N]$. An important question regarding these norms concerns for which functions they are `large’ in a certain sense.

This question has been answered fairly completely by B. Green, T. Tao and T. Ziegler in terms of certain algebraic functions called \textit{nilsequences}. In this work, we show that more explicit functions called \textit{bracket polynomials} have `large’ Gowers norm. Specifically, for a fairly large class of bracket polynomials, called \textit{constant-free bracket polynomials}, we show that if $\varphi$ is a bracket polynomial of degree $k-1$ on $[N]$, then the function $f:n\mapsto e(\varphi (n))$ has Gowers $U^k[\mathbb{N}]$-norm uniformly bounded away from zero.

We establish this result by first reducing it to a certain recurrence property of sets of constant-free bracket polynomials. Specifically, we show that if ${\theta }_1,\dots ,{\theta }_r$ are constant-free bracket polynomials, then their values, modulo 1, are all close to zero on at least some constant proportion of the points $1,\dots ,N$.

The proof of this statement relies on two deep results from the literature. The first is work of V. Bergelson and A. Leibman showing that an arbitrary bracket polynomial can be expressed in terms of a so-called \textit{polynomial sequence} on a nilmanifold. The second is a theorem of B. Green and T. Tao describing the quantitative distribution properties of such polynomial sequences.

In the special cases of the bracket polynomials ${\varphi }_{k-1}(n)={\alpha }_{k-1}{n}^{k-2}\{{\alpha }_{1}n\cdots \}$ with $k\le 5$, we give elementary alternative proofs of the fact that $\parallel {\varphi }_{k-1}{\parallel }_{U^k[\mathbb{N}]}$ is `large,’ without reference to nilmanifolds. Here we write $\{x\}$ for the fractional part of $x$, chosen to lie in $(-1/2,1/2]$.

The theory of generic smooth closed plane curves initiated by Vladimir Arnold is a beautiful fusion of topology, combinatorics, and analysis. The theory remains fairly undeveloped. We review existing methods to describe generic smooth closed plane curves combinatorially, introduce a new one, and give an algorithm for efficient computation of Arnold’s invariants. Our results provide a good source of future research projects that involve computer experiments with plane curves. The reader is not required to have background in topology and even undergraduate  students with basic knowledge of differential geometry and graph theory will easily understand our paper.

A level ($L$) is an occurrence of two consecutive equal entries in a word $w=w_1{w}_2\cdots$, while a rise ($R$) or descent ($D$) occurs when the right or left entry, respectively, is strictly larger. If $u=u_1{u}_2\cdots u_n$ and $v=v_1{v}_2\cdots v_n$ are $k$-ary words of the same given length and $1\le i\le n-1$, then there is, for example, an occurrence of $LR$ at index $i$ if $u_i=u_{i+1}$ and $v_i<v_{i+1}$, and likewise for the other possibilities. Similar terminology may be used when discussing ordered $d$-tuples of $k$-ary words of length $n$ (the set of which we’ll often denote by $[k{]}^{nd}$).

In this paper, we consider the problem of enumerating the members of $[k{]}^{nd}$ according to the number of occurrences of the pattern $\rho$, where $d\ge 1$ and $\rho$ is any word of length $d$ in the alphabet $\{L,R,D\}$. In particular, we find an explicit formula for the generating function counting the members of $[k{]}^{nd}$ according to the number of occurrences of the patterns $\rho =L^i{R}^{d-i}$, $0\le i\le d$, which, by symmetry, is seen to solve the aforementioned problem in its entirety. We also provide simple formulas for the average number of occurrences of $\rho$ within all the members of $[k{]}^{nd}$, providing both algebraic and combinatorial proofs. Finally, in the case $d=2$, we solve the problem above where we also allow for \textit{weak rises} (which we’ll denote by $R_w$), i.e., indices $i$ such that $w_i\le w_{i+1}$ in $w$. Enumerating the cases $R_w{R}_w$ and $R_w{R}_{uw}$ seems to be more difficult, and to do so, we combine the kernel method with the simultaneous use of several recurrences.

Let $G$ be a simple, connected graph with finite vertex set $V$ and edge set $E$. A depletion of $G$ is a permutation $v_1{v}_2\dots v_n$ of the elements of $V$ with the property that $v_i$ is adjacent to some member of $\{v_1,v_2,\dots ,v_{i-1}\}$ for each $i\ge 2$. Depletions model the spread of a rumor or a disease through a population and are related to heaps. In this paper, we develop techniques for enumerating the depletions of a graph.

This statistic, i.e. the sum of positions of records, has been the object of recent interest in the literature. Using the saddle point method, we obtain from the generating function of the sum of positions of records in random permutations and Cauchy’s integral formula, asymptotic results in central and non-central regions. In the non-central region, we derive asymptotic expansions generalizing some results by Kortchemski. In the central region, we obtain a limiting distribution related to Dickman’s function. This paper fits within the framework of Analytic Combinatorics.