Counting embeddings of rooted trees into families of rooted trees

Bernhard Gittenberger¹ ; Zbigniew Gołębiewski² ; Isabella Larcher¹ ; Małgorzata Sulkowska³

¹Department of Discrete Mathematics and Geometry, Technische Universität Wien
²Wrocław University of Science and Technology, Department of Fundamentals of Computer Science, Poland
³Wrocław University of Science and Technology, Department of Fundamentals of Computer Science, Poland / Université Côte d'Azur, CNRS, Inria, I3S, France

The electronic journal of combinatorics, Tome 29 (2022) no. 3

Résumé

An embedding of a rooted tree $S$ into another rooted tree $T$ is a mapping of the vertex set of $S$ into the vertex set of $T$ that is order-preserving in a certain sense, depending on the chosen tree family. Equivalently, $S$ and $T$ may be interpreted as tree-like partially ordered sets, where $S$ is isomorphic to a subposets of $T$. A good embedding is an embedding where the root of $S$ is mapped to the root of $T$. We investigate the number of good and the number of all embeddings of a rooted tree $S$ into the family of all trees of given size $n$ of a certain family of trees. The tree families considered are binary plane trees (the order of descendants matters), binary non-plane trees and rooted plane trees. We derive the asymptotic behaviour of the number of good and the number of all embeddings in all these cases and prove that the ratio of the number of good embeddings to that of all embeddings is of the order $\Theta(1/\sqrt{n})$ in all cases, where we provide the exact constants as well. Furthermore, we prove some monotonicity properties of this ratio. Finally, we comment on the case where $S$ is disconnected.

Détail

DOI : 10.37236/10760

Classification : 05C30, 05C60, 05C05, 05A15, 05A16, 60G40, 06A07
Mots-clés : tree-like partially ordered sets, good embeddings