Limits of random trees (Q2250844): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: reviewed by (P1447): Item:Q590772 |
||
Property / reviewed by | |||
Property / reviewed by: David B. Penman / rank | |||
Revision as of 23:40, 19 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Limits of random trees |
scientific article |
Statements
Limits of random trees (English)
0 references
21 July 2014
0 references
There has been much recent interest in limit objects for sequences of graphs, with the case of sparse graphs tending to be more technically problematic than the dense cases. In the paper under review, the author considers the case where an \(n\)-vertex tree \(T_{n}\) is chosen at random, with any particular \(n\)-vertex tree \(T\) with degrees \((d_{i})\) having probability \[ \mathbb{P}(T_{n}=T) =\frac{\prod_{i=1}^{n} d_{i}!}{(n-2)!{3n-3\choose n-2}} \] (the normalising constant is justified in the paper). The author shows that this sequence is convergent and describes the limit object. The proofs proceed by estimating the expected maximum degree of a tree from this model -- it is about \(\log_{3}(n)\) -- and some detailed estimates on the density of various labelled subgraphs. The approach taken is different from that in some earlier articles on the topic.
0 references
sparse graph limit
0 references
random tree
0 references