On the largest common subtree of random leaf-labeled binary trees

DOI10.1137/20M1347504MaRDI QIDQ5028357zbMATH OpenOpenAlexFDO

Authors David Aldous

Publication date 9 February 2022

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

maximum agreement subtreerandom treestochastic fragmentation

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05)

Abstract: The size of the largest common subtree (maximum agreement subtree) of two independent uniform random binary trees on $n$ leaves is known to be between orders $n^{1/8}$ and $n^{1/2}$. By a construction based on recursive splitting and analyzable by standard "stochastic fragmentation" methods, we improve the lower bound to order $$ for $$. Improving the upper bound remains a challenging problem.

Recommendations

• The maximum agreement subtree problem
• scientific article; zbMATH DE number 1974592
• Bounds on the expected size of the maximum agreement subtree for a given tree shape
• Bounds on the expected size of the maximum agreement subtree
• An improved bound on the maximum agreement subtree problem

Cites work

• Bounds on the expected size of the maximum agreement subtree
• Bounds on the expected size of the maximum agreement subtree for a given tree shape
• Commentary on ``Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem by David Aldous and Persi Diaconis
• Dirichlet and Related Distributions
• Fragmentation energy
• scientific article; zbMATH DE number 1865935 (Why is no real title available?)
• scientific article; zbMATH DE number 782630 (Why is no real title available?)
• scientific article; zbMATH DE number 3410334 (Why is no real title available?)
• On the analysis of stochastic divide and conquer algorithms
• Phylogeny. Discrete and random processes in evolution
• Probability theory of classical Euclidean optimization problems
• Random graphs.
• Recursive self-similarity for random trees, random triangulations and Brownian excursion
• Stochastic models and descriptive statistics for phylogenetic trees, from Yule to today.
• The surprising mathematics of longest increasing subsequences
• Triangulating the Circle, at Random

Cited in

(14)

• The maximum agreement subtree problem
• An algebraic view of the relation between largest common subtrees and smallest common supertrees
• On the richness of the collection of subtrees in random binary search trees
• About the largest subtree common to several X-trees
• On coincidences of tuples in a binary tree with random labels of vertices
• scientific article; zbMATH DE number 5016713 (Why is no real title available?)
• Bounds on the expected size of the maximum agreement subtree
• scientific article; zbMATH DE number 1974592 (Why is no real title available?)
• Bounds on the expected size of the maximum agreement subtree for a given tree shape
• Expected Number of Induced Subtrees Shared by Two Independent Copies of a Random Tree
• Maximum agreement subtrees and Hölder homeomorphisms between Brownian trees
• An improved lower bound on the largest common subtree of random leaf-labeled binary trees
• The likely maximum size of twin subtrees in a large random tree
• Subgraph densities and scaling limits of random graphs with a prescribed modular decomposition

This page was built for publication: On the largest common subtree of random leaf-labeled binary trees

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