← all systems · see it in The System
Metric tree (real tree, R-tree; walked as an idea)
'real trees (also called R-trees) are a class of metric spaces generalising simplicial trees'; 'A metric space X is a real tree if it is a geodesic space where every triangle is a tripod' (Real tree). 'A metric space T is a real tree if and only if T is connected and' satisfies the four-point inequality d(x,y)+d(z,w) <= max[d(x,z)+d(y,w), d(x,w)+d(y,z)] (Janson); 'Metric trees and more generally real trees are the simplest interesting examples of hyperbolic spaces as they are 0-hyperbolic' (Hyperbolic metric space).
Properties published scienceour proposal
Sourced fields, and our own readings.
| aliases | Metric tree (the shape it approximates) |
| born at | by 1974 for the four-point condition (Buneman, as cited); the R-tree formalism in group theory by 1987 (Shalen's survey, as cited) |
| born precision | decade° (the sources read do not give the first use of the term) |
| boundary | Inside: the structure as defined and held: a metric space with unique geodesic segments and no loops (every triangle a tripod; four-point condition; 0-hyperbolic), its branch points and leaves, rooting and coding by excursions, the limits that produce it, the space of all compact trees, and the random trees built on it. Outside: what it is used to describe (genealogies of branching populations, species' evolutionary distances, markets, networks, data hierarchies), the wider geometries it belongs to (metric spaces, Gromov hyperbolic spaces), and the scientists and literature that hold it. |
| nested level | An idea of mathematics held by sys:science (rung 11): the delta = 0 case of Gromov hyperbolic spaces, a kind of geodesic metric space; its projected content walked as a model (representation: true) with readings in probability (genealogies) and phylogenetics, none of them a physical reading of spacetime or a field. |
| representation | True |
| scale | social |
Measures (8) published science
| equivalent definitions in one survey | 10 (T2a-T2j, each with T1) conditions |
| leaf and branch-point degrees | leaf: 1; branch point: 3 or more connected components of the complement |
| scaling of random quadrangulations | n^(-1/4) normalising factor, suggesting fractal dimension 4 for the limit (widely believed in physics) exponent |
| Hausdorff dimension of a stable tree | alpha/(alpha-1); 2 for the CRT (alpha = 2)° dimension |
| four-point condition first stated (as cited) | 1974 year (Buneman, J. Comb. Theory B 17:48-50) |
| continuum random tree introduced | 1991 year (Aldous) |
| molecular clock in tree-based phylogenetics | child species diverge 'at a fairly constant rate' after speciation (an assumption) |
| binary phylogenetic tree degrees | root degree 2; other non-leaf vertices degree 3 edges per vertex |
Partners and parts published science
Built from / builds (4)
- Gromov hyperbolic space
- Metric space
- Simplicial trees (the discrete case they generalise)
- Geodesic segments (unique between any two points)
Sits inside / holds (2)
Trades with (valence) (7)
- Science (as a human social and cultural system) via sys:written-record · Metric tree (real tree, R-tree; walked as an idea) gain
- Hyperbolic plane via sys:spacetime · Metric tree (real tree, R-tree; walked as an idea) gain
- Gromov hyperbolic space via sys:spacetime · Metric tree (real tree, R-tree; walked as an idea) gain
- Metric space via sys:spacetime · Metric tree (real tree, R-tree; walked as an idea) gain
- Gromov-hyperbolic group (Cayley graph) via sys:spacetime · Metric tree (real tree, R-tree; walked as an idea) gain
- Ultrametric space via sys:spacetime · Metric tree (real tree, R-tree; walked as an idea) gain
- Brownian motion (Kakutani exit formula) via sys:spacetime · Metric tree (real tree, R-tree; walked as an idea) gain
expressed by (4)
- Scaffolding/Enablement (Meta-Tooling)
- Templating / Standardization
- Interoperability/Transduction (Bridging)
- Mapping/Modeling
floor filled by (19)
- Gromov hyperbolic space
- Sequential information (the order of units along a linear polymer)
- Science (as a human social and cultural system)
- Mental representation (beliefs, meanings, feelings and shared intentions)
- Metric space
- Gromov-hyperbolic group (Cayley graph)
- Ultrametric space
- Brownian motion (Kakutani exit formula)
- Simplicial trees (the discrete case they generalise)
- Hedgehog space (including the plane under the Paris metric)
- Bruhat-Tits tree of SL2 over a valued field
- Continuum random tree (Brownian tree)
- Stable trees
- Phylogenetic tree (edge-weighted)
- Phylogenetic network
- Branching populations (Galton-Watson processes; superprocesses)
- Financial market (hierarchical tree of stocks)
- Superprocess
- Brownian map
represents (6)
- Sequential information (the order of units along a linear polymer)
- Internet
- Branching populations (Galton-Watson processes; superprocesses)
- Financial market (hierarchical tree of stocks)
- Hyperbolic (Poincare) embeddings in machine learning
- the structure exists here only as an idea held by science; no rung 0-1 structure to represent (its readings are models of genealogies, phylogenies, markets and networks)
Kinds (7)
- Gromov hyperbolic space
- Simplicial trees (the discrete case they generalise)
- Random real trees
- Hedgehog space (including the plane under the Paris metric)
- Lambda-tree
- Bruhat-Tits tree of SL2 over a valued field
- Real building
Notes published science
- Zoom far enough out from any negatively curved space and only a tree is left: every asymptotic cone of a Gromov hyperbolic space is a real tree, and that property alone tells hyperbolic spaces apart. The same tree-under-everything shows up in stock markets, the Internet and machine-learning hierarchies.
- One test, four points, three fields: for any four points, two of the three pairwise sums are equal and the third is no larger. Phylogenetics uses it to ask whether species' distances fit a family tree; geometers use it (up to delta) to define hyperbolic space. Gene swapping between microbes breaks it.
- A random family tree, scaled down, has a shape of its own: the continuum random tree, coded by a Brownian excursion, where the dips of the curve are the parents of the peaks.
Layers
The ways it takes in its world, where they meet, and how it acts back, each from L1 (where it meets the world) up.
genealogies coded as random real trees (projected model on cell lineage)
- L1: Individuals and ancestral lines in a branching population; discrete Galton-Watson trees; the most recent common ancestor of two vertices
- L2: Rescaling: critical Galton-Watson trees conditioned to have n vertices converge (n -> infinity) to the continuum random tree (Aldous 1991), the tree coded by a normalised Brownian excursion; a Brownian tree is almost surely a non-simplicial real tree
- L3: Stable trees: self-similar, with a branching property analogous to Galton-Watson trees (subtrees above level a distributed as atoms of a Poisson point measure); Hausdorff dimension alpha/(alpha-1)
- L4: Spatial trees: genealogy plus spatial displacements; superprocesses as weak limits of branching particle systems coded by a continuous genealogical structure (the Brownian snake); ISE in asymptotics of statistical-mechanics models (lattice trees, percolation)
- L5: Random surfaces: large random quadrangulations and planar maps are used in theoretical physics as models of random surfaces; the n^(-1/4) scaling suggests fractal dimension 4; the Brownian map as a candidate limit built from the tree
metric tree (own: a geodesic metric space with no loops; projected model)
- L1: Points joined by unique geodesic segments: for any x, y a unique isometric embedding of [0, d(x,y)] (T1); examples: simplicial trees (graphs without cycles), the hedgehog space, the plane under the Paris metric
- L2: No loops: every triangle is a tripod; no subset homeomorphic to a circle; the four-point inequality d(x,y)+d(z,w) <= max[d(x,z)+d(y,w), d(x,w)+d(y,z)]; 0-hyperbolic in Gromov's sense
- L3: Branch points and leaves: degree = number of components of the complement; leaf 1, branch point 3 or more; simplicial exactly when the singular points are closed and discrete (a non-simplicial example: intervals of length 1/n glued along [0, 2])
- L4: Rooting and coding: a root makes each segment [[rho, sigma]] an ancestral line and gives a most recent common ancestor; any positive excursion e codes a real tree by d_e(x,y) = e(x)+e(y)-2 min e on [x,y], local minima as parents of local maxima
- L5: Limits: ultralimits of delta_i-hyperbolic spaces with delta_i -> 0 are real trees; the asymptotic cone of any hyperbolic space is a real tree (this characterises hyperbolicity); Bestvina-Paulin limits of unbounded actions are real trees (analysed by the Rips machine); the Bruhat-Tits building of SL2(F) over an ultrametric field
- L6: The space of trees: compact real trees under the Gromov-Hausdorff distance form a complete separable (Polish) metric space, so random real trees can be defined as random elements
the metric tree as held by science (mental representation)
- L1: Papers and books: Buneman 1974 (four-point condition), Shalen 1987 ('Dendrology of groups'), Aldous 1991 (CRT), Chiswell 2001 (Lambda-trees), Bestvina 2002 (handbook chapter), Evans 2005 (Saint-Flour notes), Le Gall 2005-2006 surveys, Janson's 2023 survey ('no new results')
- L2: Many equivalent definitions (T1 with T2a-T2j; tripods; no circle; four-point; 0-hyperbolic; excursion coding)
- L3: Uses inside mathematics: geometric group theory (actions on real trees, the Rips machine, degenerations of hyperbolic structures after Morgan and Shalen) and probability (random real trees, superprocesses)
- L4: Uses outside: phylogenetics (tree metrics, ultrametrics, networks when the tree fails), finance (the hierarchical tree of a market's subdominant ultrametric), networks (hyperbolic geometry underneath), machine learning (hierarchies embedded in the Poincare ball)
tree metrics between species (projected model on sequential information)
- L1: A set of species (the leaves) and evolutionary distances between them, from molecular sequences or morphology
- L2: The clock assumption: after speciation, child species diverge independently at a fairly constant rate, so an older least common ancestor means a greater distance (Zuckerkandl and Pauling 1965, as cited); with it the distances are an ultrametric (an equidistant tree)
- L3: Tree metric: the four-point condition (Buneman 1974, as cited); the path-length distance of an edge-weighted phylogenetic tree is necessarily a tree metric; the tree treated as a continuous object, each edge a real interval; ultrametric inside tree metric inside metric
- L4: Departures: recombination, horizontal gene transfer, hybridisation and introgression (reticulate evolution) call for phylogenetic networks; convergent evolution can make the distances fail the four-point condition
Sources (10) published science
Janson S. Real trees. arXiv:2303.07920 (survey; dated 8 June 2020, revised 14 March 2023; the arXiv copy was read) (behind its links)
Le Gall J-F. Random real trees. arXiv:math/0605484 (2006 survey; the arXiv copy was read) (behind its links)
Buneman P. A Note on the Metric Properties of Trees. Journal of Combinatorial Theory B 17:48-50 (1974) (cited by the encyclopedia for the four points condition; not read) (behind its links)
Holland B, Huber KT, Moulton V. A distance-based model for convergent evolution. Journal of Mathematical Biology 88:23 (2024). doi:10.1007/s00285-023-02038-9 (behind its links)
Frigerio R, Sisto A. Characterizing hyperbolic spaces and real trees. arXiv:0810.1526 (2008) (behind its links)
Krioukov D, Papadopoulos F, Kitsak M, Vahdat A, Boguna M. Hyperbolic Geometry of Complex Networks. arXiv:1006.5169 (2010) (behind its links)