Almost all trees have tribe number 2 or 3
✍ Scribed by J. Komlós; W.O.J. Moser
- Publisher
- Elsevier Science
- Year
- 1995
- Tongue
- English
- Weight
- 301 KB
- Volume
- 143
- Category
- Article
- ISSN
- 0012-365X
No coin nor oath required. For personal study only.
✦ Synopsis
Let T be a tree on n vertices, and let E <$ be a small fixed positive number. The tribe number t&) of T is the smallest integer r such that when any vertex is deleted, some r or fewer subtrees in the resulting forest together contain more than (1-e)n vertices. We prove the following, theorem: Almost all trees have tribe number 2 or 3. Let F# be the collection of the nnm2 labelled trees on a common n-element vertex set V. We say that a property P defined for all Y" holds for most trees if lim,, m [(TE&: Thas property P}I/n"-'=l.
For a given tree T and VE V, d(o) denotes the degree of u in T. When u (and all edges in T incident with u) is removed there remain d(o) subtrees of T -we call them the subtrees of u -containing mi = m*(u) vertices (1 < i < d(u)), listed in decreasing order so that ml>m2~"'>md(v) >o, ml+m2+"'+md(,)=n-1.