Logo: to the web site of Uppsala University

An (unrooted) d-ary tree is a tree in which every internal vertex has degree d+1. In this paper, we show for every fixed d≥2 that d-ary caterpillars have the minimum number of dominating sets among d-ary trees of a given order. We also determine the maximum number of dominating sets in binary trees (the special case d=2) and classify the extremal trees, which are also unique.

We characterize the extremal trees that maximize the number of almost-perfect matchings, which are matchings covering all but one or two vertices, and those that maximize the number of strong almost-perfect matchings, which are matchings missing only one or two leaves. We also determine the trees that minimize the number of maximal matchings. We apply these results to extremal problems on the weighted Hosoya index for several choices of vertex-degree-based weight function.

A B-tree is a type of search tree where every node (except possibly for the root) contains between m and 2m keys for some positive integer m, and all leaves have the same distance to the root. We study sequences of B-trees that can arise from successively inserting keys, and in particular present a bijection between such sequences (which we call histories) and a special type of increasing trees. We describe the set of permutations for the keys that belong to a given history, and also show how to use this bijection to analyse statistics associated with B-trees.

Making use of a newly developed package in the computer algebra system SageMath, we show how to perform a full asymptotic analysis by means of the Mellin transform with explicit error bounds. As an application of the method, we answer a question of Bóna and DeJonge on 132-avoiding permutations with a unique longest increasing subsequence that can be translated into an inequality for a certain binomial sum.

For a k-tree T, we prove that the maximum local mean order is attained in a k-clique of degree 1 and that it is not more than twice the global mean order. We also bound the global mean order if T has no k-cliques of degree 2 and prove that for large order, the k -star attains the minimum global mean order. These results solve the remaining problems of Stephens and Oellermann [J. Graph Theory 88 (2018), 61-79] concerning the mean order of sub-k-trees of k-trees.

Composition schemes are ubiquitous in combinatorics, statistical mechanics and probability theory. We give a unifying explanation to various phenomena observed in the combinatorial and statistical physics literature in the context of q-enumeration (this is a model where objects with a parameter of value k have a Gibbs measure/Boltzmann weight q^k ). For structures enumerated by a composition scheme, we prove a phase transition for any parameter having such a Gibbs measure: for a criticalvalue q = q_c, the limit law of the parameter is a two-parameter Mittag-Leffler distribution, while it is Gaussian in the supercritical regime (q > q_c), and it is a Boltzmann distribution in the subcritical regime (0 < q < q_c). We apply our results to fundamental statistics of lattice paths and quarter-planewalks. We also explain previously observed limit laws for pattern-restricted permutations, and a phenomenon uncovered by Krattenthaler for the wall contacts in watermelons.

For a complex number α, we consider the sum of the αth powers of subtree sizes in Galton–Watson trees conditioned to be of size n. Limiting distributions of this functional X n (α) have been determined for Re α ≠ 0, revealing a transition between a complex normal limiting distribution for Re α < 0 and a non-normal limiting distribution for Re α > 0. In this paper, we complete the picture by proving a normal limiting distribution, along with moment convergence, in the missing case Re α = 0. The same results are also established in the case of the so-called shape functional X^′_n (0),which is the sum of the logarithms of all subtree sizes; these results were obtained earlier in special cases. In addition, we prove convergence of all moments in the case Re α < 0, where this result was previously missing, and establish new results about the asymptotic mean for real α < 1/2. A novel feature for Re α = 0 is that we find joint convergence for several α to independent limits, in contrast to the cases Re α ≠ 0, where the limit is known to bea continuous function of α. Another difference from the case Re α ≠ 0 is that there is a logarithmic factor in the asymptotic variance when Re α = 0; this holds also for the shape functional.

The proofs are largely based on singularity analysis of generating functions.

Phylogenetic trees are used to model evolution: leaves are labeled to represent contemporary species (``taxa""), and interior vertices represent extinct ancestors. Informally, convex characters are measurements on the contemporary species in which the subset of species (both contemporary and extinct) that share a given state form a connected subtree. Kelk and Stamoulis [Adv. Appl. Math., 84 (2017), pp. 34--46] showed how to efficiently count, list, and sample certain restricted subfamilies of convex characters, and algorithmic applications were given. We continue this work in a number of directions. First, we show how combining the enumeration of convex characters with existing parameterized algorithms can be used to speed up exponential-time algorithms for the maximum agreement forest problem in phylogenetics. Second, we revisit the quantity _g2(T), defined as the number of convex characters on T in which each state appears on at least 2 taxa. We use this to give an algorithm with running time O(Φ ⁿ • poly(n)), where Φ ≈ 1.6181 is the golden ratio and n is the number of taxa in the input trees for computation of maximum parsimony distance on two state characters. By further restricting the characters counted by _g2(T) we open an interesting bridge to the literature on enumeration of matchings. By crossing this bridge we improve the running time of the aforementioned parsimony distance algorithm to O(1.5895ⁿ • poly(n)) and obtain a number of new results in themselves relevant to enumeration of matchings on at most binary trees.

We prove that the multiplicity of a fixed eigenvalue alpha in a random recursive tree on n vertices satisfies a central limit theorem with mean and variance asymptotically equal to mu alpha n and sigma alpha 2n respectively. It is also shown that mu alpha and sigma alpha 2 are positive for every totally real algebraic integer. The proofs are based on a general result on additive tree functionals due to Holmgren and Janson. In the case of the eigenvalue 0, the constants mu 0 and sigma 02 can be determined explicitly by means of generating functions. Analogous results are also obtained for Laplacian eigenvalues and binary increasing trees.

A fringe subtree of a rooted tree is a subtree that consists of a vertex and all its descendants. The number of distinct fringe subtrees in random trees has been studied by several authors, notably because of its connection to tree compaction algorithms. Here, we obtain a very precise result for binary search trees: it is shown that the number of distinct fringe subtrees in a binary search tree with n leaves is asymptotically equal to (c₁n)/(log n) for a constant c₁ ≈ 2.4071298335, both in expectation and with high probability. This was previously shown to be a lower bound, our main contribution is to prove a matching upper bound. The method is quite general and can also be applied to similar problems for other tree models.