Hostname: page-component-74656f9884-c52kr Total loading time: 0 Render date: 2026-11-09T11:23:05.660Z Has data issue: false hasContentIssue false
  • English
  • Français

A Ratio Inequality for Binary Trees and the Best Secretary

Published online by Cambridge University Press:  25 April 2002

GRZEGORZ KUBICKI ,
JENŐ LEHEL  and
MICHAŁ MORAYNE
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)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 11 , Issue 2 , March 2002 , pp. 149 - 161
Copyright
2002 Cambridge University Press