[2311.02255] Decks of rooted binary trees
Mathematics > Combinatorics
arXiv:2311.02255
(math)
[Submitted on 3 Nov 2023]
Title:
Decks of rooted binary trees
Authors:
Ann Clifton
Eva Czabarka
Audace Dossou-Olory
Kevin Liu
Sarah Loeb
Utku Okur
Laszlo Szekely
Kristina Wicke
View a PDF of the paper titled Decks of rooted binary trees, by Ann Clifton and 7 other authors
View PDF
Abstract:
We consider extremal problems related to decks and multidecks of rooted binary trees (a.k.a. rooted phylogenetic tree shapes). Here, the deck (resp. multideck) of a tree $T$ refers to the set (resp. multiset) of leaf induced binary subtrees of $T$. On the one hand, we consider the reconstruction of trees from their (multi)decks. We give lower and upper bounds on the minimum (multi)deck size required to uniquely encode a rooted binary tree on $n$ leaves. On the other hand, we consider problems related to deck cardinalities. In particular, we characterize trees with minimum-size as well as maximum-size decks. Finally, we present some exhaustive computations for $k$-universal trees, i.e., rooted binary trees that contain all $k$-leaf rooted binary trees as induced subtrees.
Comments:
18 pages, 14 figures
Subjects:
Combinatorics (math.CO)
MSC
classes:
05C05, 05C35, 05C60
Cite as:
arXiv:2311.02255
[math.CO]
(or
arXiv:2311.02255v1
[math.CO]
for this version)
arXiv-issued DOI via DataCite
Submission history
From: Kristina Wicke [
view email
[v1]
Fri, 3 Nov 2023 22:12:53 UTC (27 KB)
Full-text links:
Access Paper:
View a PDF of the paper titled Decks of rooted binary trees, by Ann Clifton and 7 other authors
View PDF
TeX Source
view license
Current browse context:
math.CO
< prev
next >
new
recent
2023-11
Change to browse by:
math
References & Citations
NASA ADS
Google Scholar
Semantic Scholar
export BibTeX citation
Loading...
BibTeX formatted citation
Data provided by:
Bibliographic Tools
Bibliographic and Citation Tools
Bibliographic Explorer Toggle
Bibliographic Explorer
What is the Explorer?
Connected Papers Toggle
Connected Papers
What is Connected Papers?
Litmaps Toggle
Litmaps
What is Litmaps?
scite.ai Toggle
scite Smart Citations
What are Smart Citations?
Code, Data, Media
Code, Data and Media Associated with this Article
alphaXiv Toggle
alphaXiv
What is alphaXiv?
Links to Code Toggle
CatalyzeX Code Finder for Papers
What is CatalyzeX?
DagsHub Toggle
DagsHub
What is DagsHub?
GotitPub Toggle
Gotit.pub
What is GotitPub?
Huggingface Toggle
Hugging Face
What is Huggingface?
ScienceCast Toggle
ScienceCast
What is ScienceCast?
Demos
Demos
Replicate Toggle
Replicate
What is Replicate?
Spaces Toggle
Hugging Face Spaces
What is Spaces?
Spaces Toggle
TXYZ.AI
What is TXYZ.AI?
Related Papers
Recommenders and Search Tools
Link to Influence Flower
Influence Flower
What are Influence Flowers?
Core recommender toggle
CORE Recommender
What is CORE?
Author
Venue
Institution
Topic
About arXivLabs
arXivLabs: experimental projects with community collaborators
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community?
Learn more about arXivLabs
Which authors of this paper are endorsers?
Disable MathJax
What is MathJax?