On trees, tanglegrams, and tangled chains
Tanglegrams are a class of graphs arising in computer science and in biological research on cospeciation and coevolution. They are formed by identifying the leaves of two rooted binary trees. The embedding of the trees in the plane is irrelevant for this application. We give an explicit formula to c...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2020-04-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/6348/pdf |
| _version_ | 1797270230585573376 |
|---|---|
| author | Sara Billey Matjaz Konvalinka Frderick Matsen IV |
| author_facet | Sara Billey Matjaz Konvalinka Frderick Matsen IV |
| author_sort | Sara Billey |
| collection | DOAJ |
| description | Tanglegrams are a class of graphs arising in computer science and in biological research on cospeciation and coevolution. They are formed by identifying the leaves of two rooted binary trees. The embedding of the trees in the plane is irrelevant for this application. We give an explicit formula to count the number of distinct binary rooted tanglegrams with n matched leaves, along with a simple asymptotic formula and an algorithm for choosing a tanglegram uniformly at random. The enumeration formula is then extended to count the number of tangled chains of binary trees of any length. This work gives a new formula for the number of binary trees with n leaves. Several open problems and conjectures are included along with pointers to several followup articles that have already appeared. |
| first_indexed | 2024-04-25T02:00:58Z |
| format | Article |
| id | doaj.art-b92a67362088450f9ef28183814f7fe7 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:00:58Z |
| publishDate | 2020-04-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-b92a67362088450f9ef28183814f7fe72024-03-07T14:55:20ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502020-04-01DMTCS Proceedings, 28th...10.46298/dmtcs.63486348On trees, tanglegrams, and tangled chainsSara Billey0Matjaz Konvalinka1Frderick Matsen IVDepartment of Mathematics [Seattle]Departement of Mathematics [Slovenia]Tanglegrams are a class of graphs arising in computer science and in biological research on cospeciation and coevolution. They are formed by identifying the leaves of two rooted binary trees. The embedding of the trees in the plane is irrelevant for this application. We give an explicit formula to count the number of distinct binary rooted tanglegrams with n matched leaves, along with a simple asymptotic formula and an algorithm for choosing a tanglegram uniformly at random. The enumeration formula is then extended to count the number of tangled chains of binary trees of any length. This work gives a new formula for the number of binary trees with n leaves. Several open problems and conjectures are included along with pointers to several followup articles that have already appeared.https://dmtcs.episciences.org/6348/pdf[math.math-co]mathematics [math]/combinatorics [math.co] |
| spellingShingle | Sara Billey Matjaz Konvalinka Frderick Matsen IV On trees, tanglegrams, and tangled chains Discrete Mathematics & Theoretical Computer Science [math.math-co]mathematics [math]/combinatorics [math.co] |
| title | On trees, tanglegrams, and tangled chains |
| title_full | On trees, tanglegrams, and tangled chains |
| title_fullStr | On trees, tanglegrams, and tangled chains |
| title_full_unstemmed | On trees, tanglegrams, and tangled chains |
| title_short | On trees, tanglegrams, and tangled chains |
| title_sort | on trees tanglegrams and tangled chains |
| topic | [math.math-co]mathematics [math]/combinatorics [math.co] |
| url | https://dmtcs.episciences.org/6348/pdf |
| work_keys_str_mv | AT sarabilley ontreestanglegramsandtangledchains AT matjazkonvalinka ontreestanglegramsandtangledchains AT frderickmatseniv ontreestanglegramsandtangledchains |