Speaker: Eitan Bachmat (Ben-Gurion University)

Title: On Random posets of a geometric origin

Abstract: 
---------
We introduce a notion of a random poset of geoemtric origin (rapogo?). 

Such an object consists of the choice of a subset $A$ of Euclidean space,
a probability distribution $\mu $ on $A$ and for each $v\in A$, a set
$V_v$ of "visible points" such that the relation ,$R(v,w)$ iff $v\in V_w$,
defines a partial order on $A$. 

If we choose $N$ points from $A$ according to the probability distribution
$\mu $ we say that the induced poset structure on the $N$ points is a
random poset of geometric origin. 

We wish to study the behavior as $N$ tends to infinity of "natural" random
variables defined on these posets. 

The classical example is that of $A$ being the unit square in the plane,
$\mu$ the standard measure on $A$ and $V_v$ being the first quadrant
centered at $v$. The natural random variable, size of the maximal chain,
is equivalent to the random variable describing the length of the maximal
increasing subsequence of a random permutation. This variable has been
studied intensivly for the past 4 decades with some magnificant recent
results. In this talk we will consider several other examples which are
motivated by disk scheduling problems and airplane boarding problems. A
basic ingredient of Several of our results is a theorem of Deuschel and
Zeitouni on the size of the maximal increasing subsequence for general
sets $A$ with general distribution $\mu $. 

We will review this result and many others and show how they can be
applied to solve "real world" problems. 

The work in progress on airplane boarding policies is joint with S.Skiena
of Stony Brook and D.Berend and L.Sapir of BGU