Sub-trees of a random tree

DOI10.1016/J.DAM.2019.05.003MaRDI QIDQ2274085zbMATH OpenOpenAlexFDO

Authors Paweł Prałat, Bogumił Kamiński

Publication date 19 September 2019

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1808.04948

zbMATH Keywords

Galton-Watson treerandom Cayley tree

Mathematics Subject Classification ID

Trees (05C05) Enumeration in graph theory (05C30) Random graphs (graph-theoretic aspects) (05C80)

Abstract: Let $T$ be a random tree taken uniformly at random from the family of labelled trees on $n$ vertices. In this note, we provide bounds for $c(n)$, the number of sub-trees of $T$ that hold asymptotically almost surely. With computer support we show that $1.41805386^{n}lec(n)le1.41959881^n$. Moreover, there is a strong indication that, in fact, $c(n)le1.41806183^n$.

Recommendations

• On the subtrees of random binary search trees
• Models of random subtrees of a graph
• On random trees
• On subtrees of trees
• Building uniformly random subtrees
• Distinct fringe subtrees in random trees
• Repeated fringe subtrees in random rooted trees
• On the probability that a random subtree is spanning
• Random Trees in Random Graphs

Cites work

• A derivation of the Borel distribution
• Additive tree functionals with small toll functions and subtrees of random trees
• Binary trees with the largest number of subtrees
• Julia: a fresh approach to numerical computing
• Largest Number of Subtrees of Trees with a Given Maximum Degree
• Non-fringe subtrees in conditioned Galton-Watson trees
• On subtrees of trees
• On the height of trees
• Probability on trees and networks
• The number of subtrees of trees with given degree sequence

Cited in

(13)

• Almost all trees have tribe number 2 or 3
• On subtree number index of generalized book graphs, fan graphs, and wheel graphs
• On the number of transversals in random trees
• On the distribution of subtree orders of a tree
• scientific article; zbMATH DE number 3849252 (Why is no real title available?)
• Phase Changes in Subtree Varieties in Random Recursive and Binary Search Trees
• On the number of trees in Z^d
• scientific article; zbMATH DE number 398957 (Why is no real title available?)
• On the number of nonisomorphic subtrees of a tree
• Repeated fringe subtrees in random rooted trees
• Random subtrees and unimodal sequences in graphs
• Binary subtrees with few labeled paths
• On the probability of occurence of labelled subtrees of a randomly labelled tree

Describes a project that uses

Uses Software

• Julia

This page was built for publication: Sub-trees of a random tree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2274085)