Abstract
For cursive Greek chi,y elements of some (finite) poset P, write p(cursive Greek chi<y) for the probability that cursive Greek chi precedes y in a random (uniform) linear extension of P. For u, υ∈ [0,1] define δ(u,υ) = inf{p(cursive Greek chi < z) : p(cursive Greek chi < y) ≥ u, p(y < z) ≥ υ}, where the infimum is over all choices of P and distinct cursive Greek chi, y, z∈P. Addressing an issue raised by Fishburn [6], we give the first nontrivial lower bounds on the function δ. This is part of a more general geometric result, the exact determination of the function γ(u,υ) = inf{Pr(X1 < X3) : Pr(X1 < X2) ≥ u, Pr(X2 < X3) ≥ υ}, where the infimum is over X = (X1,. . .,Xn) chosen uniformly from some compact convex subset of a Euclidean space. These results are mainly based on the Brunn-Minkowski Theorem and a theorem of Keith Ball [1], which allow us to reduce to a 2-dimensional version of the problem.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 85-99 |
| Number of pages | 15 |
| Journal | Combinatorica |
| Volume | 18 |
| Issue number | 1 |
| DOIs | |
| State | Published - 1998 |
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Computational Mathematics