When bad things happen to good trees
Downloadable Content
Abstract
- When the edges in a tree or rooted tree fail with a certain fixed probability, the (greedoid) rank may drop. We compute the expected rank as a polynomial in p and as a real number under the assumption of uniform distribution. We obtain several different expressions for this expected rank polynomial for both trees and rooted trees, one of which is especially simple in each case. We also prove two extremal theorems that determine both the largest and smallest values for the expected rank of a (rooted or unrooted) tree, and precisely when these extreme bounds are achieved. We conclude with directions for further study.
| Title | When bad things happen to good trees |
|---|---|
| Creator | Graveman, W. |
| Aivaliotis, N. | |
| Gordon, Gary | |
| Publisher | Journal of Graph Theory |
| Academic Department | Mathematics |
| Division | Natural Sciences |
| Organization | Lafayette College |
| Date Issued | June 2001 |
| Date Available | 2015-05-08T19:41:43Z |
| Type | Article |
| Language | English |
| Keyword | expected rank polynomial |
| antimatroid | |
| Bibliographic Citation | Aivaliotis, N., G. Gordon, and W. Gravemen. "When bad things happen to good trees." Journal of Graph Theory 37 (2): 79-99. |
| Standard Identifier | DOI 10.1002/jgt.1004 |
| Handle 10385/1876 | |
| Permalink | http://hdl.handle.net/10385/1876 |
| Rights Statement |
In Copyright
|
| Rights Holders | John Wiley & Sons, Inc. |
Contains
| File | Gordon-JournalofGraphTheory-vol37-no2-2001.pdf | Uploaded 2019-10-20 | Public | Download |
Member of Collection
