Partial order complementation graphs |
| |
| Authors: | Jason I Brown Stephen Watson |
| |
| Institution: | 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 Pos
n
consisting of all nonempty partial orders on {1,  ,n} with edges denoting complementation. We investigate here properties of the graphs Pos
n
. In particular, we show:| – |
 The diameter of Pos
n
is 5 for alln>2 (and hence Pos
n
is connected for alln);
| | – |
With probability 1, the distance between two members of Pos
n
is 2;
| | – |
The graphs Pos
n
are universal (i.e. every graph occurs as an induced subgraph of some Pos
n
);
| | – |
The maximal size  (n) of an independent set of Pos
n
satisfies the asymptotic formula
|
| |
