Joshua Cooper
Department of Mathematics
University of South Carolina

Random Linear Extensions of Grids

A grid poset -- or "grid" for short -- is a product of chains. We ask, what does a random linear extension of a grid look like? This problem generalizes now-classical work on random plane partitions, and has surprising connections with the theory of random Ferrer diagrams, poset order dimension, representability theory in qualitative probability, and conjoint analysis (a subfield of marketing research). We show that the average "jump number," i.e., the number of times that two consecutive elements in a linear extension are incomparable in the poset, is close to its maximum possible value. The techniques employed rely on entropy arguments. We mention several interesting questions about this wide-open area.


Friday, March 23, E1 106, 3:15pm

Last updated by skougeo AT iit DOT com on 03/08/07