Logo: to the web site of Uppsala University

We consider the number of common edges in two independent random spanning trees of a graph 𝐺. For complete graphs 𝐾𝑛, we give a new proof of the fact, originally obtained by Moon, that the distribution converges to a Poisson distribution with expected value 2. This is applied to show a Poisson limit law for the number of common edges in two independent random spanning trees of an Erdős–Rényi random graph 𝐺⁡(𝑛,𝑝) for constant 𝑝, as well as a central limit theorem in the case where 𝑝 → 0 and 𝑝≥𝑛^−2/3+ɛ. We also use the same method to prove an analogous result for complete multipartite graphs.

Making use of a newly developed package in the computer mathematics system SageMath, we show how to perform a full asymptotic analysis of certain types of sums that occur frequently in combinatorics, including explicit error bounds. We present two applications of the general approach to illustrate its use: the first concerns a classical problem due to Ramanujan, while the second one concerns 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.

A binary tree (more precisely, an unrooted binary tree) is a tree in which all internal vertices (i.e., non-leaves) are exactly of degree 3. We give an upper bound and a lower bound for the number of maximal independent sets in binary trees together with a characterization of the extremal binary trees. The binary trees with second largest number of maximal independent sets are also characterized. (c) 2025 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).

In this paper we present new results on the enumeration of parking functions and labeled forests. We introduce new statistics on parking functions, which are then extended to labeled forests via bijective correspondences. We determine the joint distribution of two statistics on parking functions and their counterparts on labeled forests. Our results on labeled forests also serve to explain the mysterious equidis-tribution between two seemingly unrelated statistics in parking functions recently identified by Stanley and Yin and give an explicit bijection between the two statistics. Extensions of our techniques are discussed, including joint distribution on further refinement of these new statistics.

We consider the asymptotic enumeration of labelled acyclic digraphs (DAGs) with the additional restriction of being bipartite. The analysis leads us to a meromorphic generating function in two variables for the number of bicoloured labelled DAGs whose analysis falls within the scope of analytic combinatorics in several variables. This allows us to obtain asymptotic formulas for the total number of labelled bipartite DAGs with a given number of vertices as well as for the number of such DAGs with a given bipartition (i.e., with prescribed sizes of the two partite sets).

In this paper we study cycles in multiset permutations and parking functions. As combinatorial objects, multiset permutations are essential building blocks for mappings and permutations, while parking functions lie between mappings and permutations. We take both algebraic and analytic views in our investigation and present exact as well as asymptotic results. We point to a surprising correspondence between two statistics on multiset permutations, terminal closers and cyclic points, shedding light on the combinatorial structure.

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.

We consider two closely related concepts in rooted trees: the path length is the sum of all distances from the root to the vertices of the tree, while the external path length is the sum of all distances from the root to the leaves of the tree. Upon dividing by the number of vertices and leaves respectively, we obtain the average distance to the root. For two important classes of random trees, we show that the average distance of the root to a random leaf is almost the same as the average distance to a random vertex. For Bienaymé-Galton-Watson trees, the difference is bounded in probability. For three varieties of increasing trees (recursive trees, d-ary increasing trees, generalised plane-oriented recursive trees), on the other hand, the difference converges to a constant in probability.

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.

An (unrooted) binary tree is a tree in which every internal vertex has degree . In this paper, we determine the minimum and maximum number of total dominating sets in binary trees of a given order. The corresponding extremal binary trees are characterized as well. The minimum is always attained by the binary caterpillar, while the binary trees that attain the maximum are only unique when the number of vertices is not divisible by~4. Moreover, we obtain a lower bound on the number of total dominating sets for -ary trees and characterize the extremal trees as well.