PDFLINK |

# Trees in Many Contexts

The authors of this piece are organizers of the AMS 2022 Mathematics Research Communities summer conference *Trees in Many Contexts*, one of four topical research conferences offered this year that are focused on collaborative research and professional development for early-career mathematicians. Additional information can be found at https://www.ams.org/programs/research-communities/2022MRC-Trees. Applications are open until February 15, 2022.

Trees are one of the most fundamental classes of graphs. They play a key role in graph theory and combinatorics, but also occur in many other contexts within mathematics as well as other sciences, such as biology, chemistry, and computer science.

Trees have a very simple structure, so many graph-theoretical problems that are otherwise very difficult can be solved for trees, and algorithmic questions that are computationally hard for general graphs often have simple efficient solutions. At the same time, there are also notoriously hard problems that specifically concern trees, for example *Ringel’s conjecture*, which states that the complete graph can be decomposed into edge-disjoint copies of any given tree with vertices. This conjecture was only verified very recently for large 9.

An example of a problem on trees that is completely open is *Graham’s tree reconstruction conjecture*: starting from a tree take the line graph , (the graph whose vertices are the edges of and where two vertices are adjacent if and only if the corresponding edges are adjacent in and its iterates ) , , …. Graham’s tree reconstruction conjecture states that the sequence of orders , , , … uniquely determines , Not much is known about this conjecture. Recent progress .3 shows that the number of trees with vertices that are uniquely determined is at least but this is still far from the number of different trees, which grows exponentially with , .

These examples already illustrate the variety of interesting problems that deal with trees, and also show that trees are only superficially simple and easy to understand.

## Trees in Biology

In biology, trees occur prominently as *phylogenetic trees* that illustrate the evolutionary relationships among different species. The species correspond to the leaves of the tree, and the root (if there is one) to the most recent common ancestor. Mathematical problems involving phylogenetic trees are often motivated by computational applications.

A typical example to illustrate the type of questions that arise in this context concerns *maximum agreement subtrees*. Here, one considers leaf-labeled binary trees, where the leaves are labeled , …, , (one can think of them as representing different species). A binary tree can be restricted to a subset of leaves in a natural way: one takes the smallest subtree that contains all these leaves, then one suppresses all vertices of degree to obtain a new binary tree.

Two leaf-labeled trees and with vertices are said to *agree* on a subset of if the respective restrictions to are the same (i.e., there is a label-preserving isomorphism). For example, the two trees in Figure 1 agree on the set The maximum size of a set . on which and agree is denoted This quantity is similar, for example, to the longest common subsequence of two strings or permutations. It was an open question until recently how small . could be in terms of the number of leaves In his recent paper .6, Markin established that the minimum is in fact of order by improving the previous lower bound that was of order 7.

For pairs of *random trees*, the order of magnitude of the average size of a maximum agreement subtree is still unknown. Upper bounds of hold for both standard models in phylogenetics, the uniform model and the Yule-Harding model. On the other hand, Bernstein, Ho, Long, Steel, St. John, and Sullivant 1 provided lower bounds of (uniform model) and (Yule-Harding). Simulations suggest that the true exponent is close to see ;2. For random trees of the same shape (but different labels), it was shown recently 8 that the order of the expected size is .

## Trees in Chemistry

Chemistry has influenced combinatorial mathematics for a long time, an early example being the enumeration of chemical compounds, which was an explicit motivation in Pólya’s ground-breaking work 10 on what is now known as *Pólya’s enumeration method*. Trees play a prominent role in this context as models for acyclic molecules. For example, there are three skeletal isomers of pentane which correspond to the isomorphism classes of trees with five vertices, as shown in Figure ,2.

The field of *chemical graph theory* has seen a lot of growth in recent years, which is also evidenced by the inclusion of two new MSC codes in the 2020 edition: *chemical graph theory* 05C92 and *graphical indices* 05C09. Graphical indices (also called *topological indices* after an early example that is now known as Hosoya index) are invariants (usually integers or real numbers) associated with graphs. In many instances, it has been observed that these indices are well correlated with physico-chemical properties of the corresponding molecules.

A prominent instance is the *Wiener index* of a graph, which is defined as the sum of the distances between all pairs of vertices. It was introduced by Harry Wiener in his 1947 paper 13 as the *path number* in connection with paraffin boiling points. As Wiener notices in passing, it can be calculated for trees as follows: for each edge take the product of the cardinalities of the two components that result when , is removed. Then sum all the resulting products. It is easy to see that the product represents the number of times occurs on a (shortest) path between two vertices, so this sum is indeed equal to the Wiener index. This simple—yet elegant and useful—property of the Wiener index is an early example of a theorem in chemical graph theory that actually appeared in a chemistry journal.

There are many different aspects to current chemical graph theory, but most commonly, researchers are interested in bounds for various indices associated with graphs, relations between different indices, and extremal questions where the maximum or minimum of an index for a specific family of graphs (for instance, all trees with vertices) are sought. Trees traditionally play a prominent role in this context, as do various types of tree-like graphs that are relevant in chemistry, e.g., graphs with a limited number of cycles or cycles of specific lengths such as hexagons. Certain structures occur repeatedly in this context; unsurprisingly, for instance, path and star are typically the trees for which minimum and maximum of a graphical index are attained. Another example is *greedy trees* that frequently occur when degree restrictions are imposed; see for example 12, Sections 2.6.2 and 3.2.1.

## Trees in Computer Science

Trees are useful as a data structure and form the basis of many algorithms; see for example 5, Section 2.3. For example, trees store hierarchical data and can be used for searching and sorting. *Binary search trees* are a typical example of a tree data structure, and they are also connected to the well-known *Quicksort* algorithm. In a binary search tree, labels in the left root branch are all smaller than the root label while labels in the right root branch are all greater. The same applies to the two branches at all other vertices.

Trees have been studied for a long time in the context of worst-case and average-case analysis of algorithms; see for example 11, Chapter 6. Parameters like the *height* (greatest distance from the root to a leaf) are measures for the performance of algorithms. Within this context, enumerative problems concerning trees and tree-like structures as well as properties of *random trees* are often of interest, especially when average-case performance of algorithms is considered. There are many different ways to generate trees at random, and the structural properties often differ depending on the specific model of randomness that is used. The simplest and most straightforward way to generate trees at random is perhaps *uniform models*, in which a tree is selected uniformly at random from all trees with vertices from a given family.

A classical way to generate trees by a random process is *Galton-Watson trees*: these trees start with a root and a given offspring distribution. In the step, all vertices of generation th independently produce offspring according to that distribution. Galton-Watson trees and uniformly random trees are models where typical trees with vertices have height of order .

Other models produce trees where the height is typically only of logarithmic order: examples include random binary search trees (whose probabilistic model is in fact equivalent to the aforementioned Yule-Harding model in phylogenetics) and *recursive trees*, where one starts with a single vertex and the vertex is attached to one of the previous th vertices uniformly at random. The height is only one of the many structural properties of trees that have been studied for many different types of random trees. Very precise results not only on the order of magnitude, but also the distribution, are often available 4.

## Conclusion

This brief introduction aims to show in what different contexts trees and tree structures occur and what mathematical questions around trees are of interest in different fields. Its intention is also to give a flavor of the type of problems that will be investigated at the upcoming AMS MRC *Trees in Many Contexts*.

## Acknowledgment

Stephan Wagner is supported by the Knut and Alice Wallenberg Foundation.

## References

- [1]
- Daniel Irving Bernstein, Lam Si Tung Ho, Colby Long, Mike Steel, Katherine St. John, and Seth Sullivant,
*Bounds on the expected size of the maximum agreement subtree*, SIAM J. Discrete Math.**29**(2015), no. 4, 2065–2074, DOI 10.1137/140997750. MR3416130Show rawAMSref`\bib{bernstein2015}{article}{ author={Bernstein, Daniel Irving}, author={Ho, Lam Si Tung}, author={Long, Colby}, author={Steel, Mike}, author={St. John, Katherine}, author={Sullivant, Seth}, title={Bounds on the expected size of the maximum agreement subtree}, journal={SIAM J. Discrete Math.}, volume={29}, date={2015}, number={4}, pages={2065--2074}, issn={0895-4801}, review={\MR {3416130}}, doi={10.1137/140997750}, }`

Close amsref.^{✖} - [2]
- David Bryant, Andy McKenzie, and Mike Steel,
*The size of a maximum agreement subtree for random binary trees*, Bioconsensus (Piscataway, NJ, 2000/2001), DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 61, Amer. Math. Soc., Providence, RI, 2003, pp. 55–65, DOI 10.1090/dimacs/061/04. MR1982419Show rawAMSref`\bib{bryant2003}{article}{ author={Bryant, David}, author={McKenzie, Andy}, author={Steel, Mike}, title={The size of a maximum agreement subtree for random binary trees}, conference={ title={Bioconsensus}, address={Piscataway, NJ}, date={2000/2001}, }, book={ series={DIMACS Ser. Discrete Math. Theoret. Comput. Sci.}, volume={61}, publisher={Amer. Math. Soc., Providence, RI}, }, date={2003}, pages={55--65}, review={\MR {1982419}}, doi={10.1090/dimacs/061/04}, }`

Close amsref.^{✖} - [3]
- Joshua Cooper, Bill Kay, and Anton Swifton,
*Graham’s tree reconstruction conjecture and a Waring-type problem on partitions*, J. Comb.**9**(2018), no. 3, 469–488, DOI 10.4310/JOC.2018.v9.n3.a3. MR3809644Show rawAMSref`\bib{cooper2018}{article}{ author={Cooper, Joshua}, author={Kay, Bill}, author={Swifton, Anton}, title={Graham's tree reconstruction conjecture and a Waring-type problem on partitions}, journal={J. Comb.}, volume={9}, date={2018}, number={3}, pages={469--488}, issn={2156-3527}, review={\MR {3809644}}, doi={10.4310/JOC.2018.v9.n3.a3}, }`

Close amsref.^{✖} - [4]
- Michael Drmota,
*Random trees*:*An interplay between combinatorics and probability*, SpringerWienNewYork, Vienna, 2009, DOI 10.1007/978-3-211-75357-6. MR2484382Show rawAMSref`\bib{drmota2009}{book}{ author={Drmota, Michael}, title={Random trees}, subtitle={An interplay between combinatorics and probability}, publisher={SpringerWienNewYork, Vienna}, date={2009}, pages={xviii+458}, isbn={978-3-211-75355-2}, review={\MR {2484382}}, doi={10.1007/978-3-211-75357-6}, }`

Close amsref.^{✖} - [5]
- Donald E. Knuth,
*The art of computer programming. Vol. 1*:*Fundamental algorithms*, Addison-Wesley, Reading, MA, 1997. Third edition [of MR0286317]. MR3077152Show rawAMSref`\bib{knuth1997}{book}{ author={Knuth, Donald E.}, title={The art of computer programming. Vol. 1}, subtitle={Fundamental algorithms}, note={Third edition [of MR0286317]}, publisher={Addison-Wesley, Reading, MA}, date={1997}, pages={xx+650}, isbn={0-201-89683-4}, review={\MR {3077152}}, }`

Close amsref.^{✖} - [6]
- Alexey Markin,
*On the extremal maximum agreement subtree problem*, Discrete Appl. Math.**285**(2020), 612–620, DOI 10.1016/j.dam.2020.07.007. MR4124794Show rawAMSref`\bib{Markin2020}{article}{ author={Markin, Alexey}, title={On the extremal maximum agreement subtree problem}, journal={Discrete Appl. Math.}, volume={285}, date={2020}, pages={612--620}, issn={0166-218X}, review={\MR {4124794}}, doi={10.1016/j.dam.2020.07.007}, }`

Close amsref.^{✖} - [7]
- Daniel M. Martin and Bhalchandra D. Thatte,
*The maximum agreement subtree problem*, Discrete Appl. Math.**161**(2013), no. 13-14, 1805–1817, DOI 10.1016/j.dam.2013.02.037. MR3056987Show rawAMSref`\bib{Martin2013}{article}{ author={Martin, Daniel M.}, author={Thatte, Bhalchandra D.}, title={The maximum agreement subtree problem}, journal={Discrete Appl. Math.}, volume={161}, date={2013}, number={13-14}, pages={1805--1817}, issn={0166-218X}, review={\MR {3056987}}, doi={10.1016/j.dam.2013.02.037}, }`

Close amsref.^{✖} - [8]
- Pratik Misra and Seth Sullivant,
*Bounds on the expected size of the maximum agreement subtree for a given tree shape*, SIAM J. Discrete Math.**33**(2019), no. 4, 2316–2325, DOI 10.1137/18M1213695. MR4036089Show rawAMSref`\bib{misra2019}{article}{ author={Misra, Pratik}, author={Sullivant, Seth}, title={Bounds on the expected size of the maximum agreement subtree for a given tree shape}, journal={SIAM J. Discrete Math.}, volume={33}, date={2019}, number={4}, pages={2316--2325}, issn={0895-4801}, review={\MR {4036089}}, doi={10.1137/18M1213695}, }`

Close amsref.^{✖} - [9]
- R. Montgomery, A. Pokrovskiy, and B. Sudakov,
*A proof of Ringel’s conjecture*, Geom. Funct. Anal.**31**(2021), no. 3, 663–720, DOI 10.1007/s00039-021-00576-2. MR4311581Show rawAMSref`\bib{montgomery2021}{article}{ author={Montgomery, R.}, author={Pokrovskiy, A.}, author={Sudakov, B.}, title={A proof of Ringel's conjecture}, journal={Geom. Funct. Anal.}, volume={31}, date={2021}, number={3}, pages={663--720}, issn={1016-443X}, review={\MR {4311581}}, doi={10.1007/s00039-021-00576-2}, }`

Close amsref.^{✖} - [10]
- G. Pólya,
*Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen*(German), Acta Math.**68**(1937), no. 1, 145–254, DOI 10.1007/BF02546665. MR1577579Show rawAMSref`\bib{Polya1937}{article}{ author={P\'{o}lya, G.}, title={Kombinatorische Anzahlbestimmungen f\"{u}r Gruppen, Graphen und chemische Verbindungen}, language={German}, journal={Acta Math.}, volume={68}, date={1937}, number={1}, pages={145--254}, issn={0001-5962}, review={\MR {1577579}}, doi={10.1007/BF02546665}, }`

Close amsref.^{✖} - [11]
- Robert Sedgewick and Philippe Flajolet,
*An introduction to the analysis of algorithms*, Addison-Wesley-Longman, 1996.Show rawAMSref`\bib{sedgewick1996}{book}{ author={Sedgewick, Robert}, author={Flajolet, Philippe}, title={An introduction to the analysis of algorithms}, publisher={Addison-Wesley-Longman}, date={1996}, isbn={978-0-201-40009-0}, }`

Close amsref.^{✖} - [12]
- Stephan Wagner and Hua Wang,
*Introduction to chemical graph theory*, Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, FL, 2019. MR3837106Show rawAMSref`\bib{wagner2019}{book}{ author={Wagner, Stephan}, author={Wang, Hua}, title={Introduction to chemical graph theory}, series={Discrete Mathematics and its Applications (Boca Raton)}, publisher={CRC Press, Boca Raton, FL}, date={2019}, pages={x+259}, isbn={978-1-138-32508-1}, review={\MR {3837106}}, }`

Close amsref.^{✖} - [13]
- H. Wiener,
*Structural determination of paraffin boiling points*, J. Am. Chem. Soc.**69**(1947), 17–20.Show rawAMSref`\bib{wiener1947}{article}{ author={Wiener, H.}, title={Structural determination of paraffin boiling points}, date={1947}, journal={J. Am. Chem. Soc.}, volume={69}, pages={17\ndash 20}, }`

Close amsref.^{✖}