Limits of random trees (Q2250844): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(6 intermediate revisions by 5 users not shown) | |||
Property / reviewed by | |||
Property / reviewed by: David B. Penman / rank | |||
Property / reviewed by | |||
Property / reviewed by: David B. Penman / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2066540443 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 1401.2521 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The continuum random tree. III / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Recurrence of distributional limits of finite planar graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Asymptotic Enumeration of Spanning Trees / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 19:24, 8 July 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