Centre for Discrete and Applicable Mathematics

 CDAM Research Report, LSE-CDAM-97-16

December 1997

Forbidden Induced Partial Orders

Graham Brightwell, David A. Grable, and Hans Jürgen Prömel


For each finite partial order P, we consider the size of the set  Forbindn(P)  of partial orders on n labelled points containing no induced copy of P. We show that  |Forbindn(P)| = 2o(n2)  unless P has height at least 3, in which case  |Forbindn(P)| = 2n2/4+o(n2).  We show that  |Forbindn(P)| <= nc  for some constant c if and only if P is either an antichain or one of ten small partial orders. Between these extremes, we consider the question of which P have  |Forbindn(P)| = nO(n).

If you would like a free copy of this report, please send the number of this report, LSE-CDAM-97-16, together with your name and postal address to:
CDAM Research Reports Series
Centre for Discrete and Applicable Mathematics
London School of Economics
Houghton Street
London WC2A 2AE, U.K.
Phone: +44(0)-171-955 7732.
Fax: +44(0)-171-955 6877.
Email: info@maths.lse.ac.uk

Introduction to the CDAM Research Report Series.
CDAM Homepage.

Copyright © London School of Economics & Political Science 2005

Last changed: Wed 9 Feb 2005
For comments go to: http://www.maths.lse.ac.uk/webmaster.html