Princeton Discrete Math Seminar


Geometry and poset probabilities


Jeff Kahn
Rutgers University


Fine Hall 214
Princeton University


3:00 p.m.
Thursday, April 17, 1997

We consider uniform distribution on the set of linear extensions of a finite poset P. (A linear extension of P is a linear ordering of the elements of P extending the order in P.)

Probabilities associated with such distributions are the subject of several fascinating conjectures, some originating in questions about sorting. Curiously, progress on these questions has usually involved application of various tools from other parts of mathematics, especially geometry.

We will survey some of these developments, and mention one new result (joint with Yang Yu and answering a 1986 question of Peter Fishburn), a special case of which says:

If x,y,z are elements of P for which Pr(x < y) > 1/2 and Pr(y < z) > 1/2, then Pr(x < z) > 1/4.

(Note nothing similar is true if we replace 1/2 by .499.)

Next week: TBA

Document last modified on April 11, 19997