Hostname: page-component-745bb68f8f-b95js Total loading time: 0 Render date: 2025-01-10T22:16:07.175Z 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: [email protected])
JENŐ LEHEL
Affiliation:
Department of Mathematics, University of Louisville, Louisville, KY 40292, USA (e-mail: [email protected])
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: [email protected])
Get access Rights & Permissions [Opens in a new window]

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
Combinatorics, Probability and Computing , Volume 11 , Issue 2 , March 2002 , pp. 149 - 161
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.)