Article contents
A Ratio Inequality for Binary Trees and the Best Secretary
Published online by Cambridge University Press: 25 April 2002
Abstract
Let Tn be the complete binary tree of height n considered as the Hasse diagram of a poset with its root 1n as the maximum element. Define A(n; T) = [mid ]{S ⊆ Tn : 1n ∈ S, S ≅ T}[mid ], and B(n; T) = [mid ]{S ⊆ Tn : 1n ∉ S, S ≅ T}[mid ]. In this note we prove that for any fixed n and rooted binary trees T1, T2 such that T2 contains a subposet isomorphic to T1. We conjecture that the ratio A/B also increases with T for arbitrary trees. These inequalities imply natural behaviour of the optimal stopping time in a poset extension of the secretary problem.
- Type
- Research Article
- Information
- Copyright
- 2002 Cambridge University Press
- 4
- Cited by