Partial order complementation graphs |
| |
| Authors: | Jason I. Brown Stephen Watson |
| |
| Affiliation: | 1. Department of Mathematics, Statistics and Computing Science, Dalhousie University, Halifax, Nova Scotia, Canada
2. Department of Mathematics and Statistics, York University, North York, Ontario, Canada
|
| |
| Abstract: | Two partial ordersP andQ on a setX arecomplementary (written asP Q) if they share no ordered pairs (except for loops) but the transitive closure of the union is all possible ordered pairs. For each positive integern we form a graph Posn consisting of all nonempty partial orders on {1,  ,n} with edges denoting complementation. We investigate here properties of the graphs Posn. In particular, we show:| |  The diameter of Posn is 5 for alln>2 (and hence Posn is connected for alln); | | | With probability 1, the distance between two members of Posn is 2; | | | The graphs Posn are universal (i.e. every graph occurs as an induced subgraph of some Posn); | | | The maximal size  (n) of an independent set of Posn satisfies the asymptotic formula
|
| |
