Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-17T03:29:00.225Z Has data issue: false hasContentIssue false

A Ratio Inequality for Binary Trees and the Best Secretary

Published online by Cambridge University Press:  25 April 2002

GRZEGORZ KUBICKI
Affiliation:
Department of Mathematics, University of Louisville, Louisville, KY 40292, USA (e-mail: gkubicki@louisville.edu)
JENŐ LEHEL
Affiliation:
Department of Mathematics, University of Louisville, Louisville, KY 40292, USA (e-mail: gkubicki@louisville.edu)
MICHAŁ MORAYNE
Affiliation:
Institute of Mathematics, Wrocław University of Technology, Wybrzeże Wyspiańskiego 27, 50–370 Wrocław, Poland and Institute of Mathematics, Polish Academy of Sciences, Kopernika 18, 51–617 Wrocław, Poland (e-mail: morayne@mazur.im.pwr.wroc.pl)

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 ]{STn : 1nS, ST}[mid ], and B(n; T) = [mid ]{STn : 1nS, ST}[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
Copyright
2002 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)