The size of k-pseudotrees Original Research Article

Let X be a finite set. A k-pseudotree on X is a family Fof subsets of X such that: (i) X ϵ F and for every xϵ X, {x} ϵ F; (ii) for every U ϵ F there exists an xϵU such that if V ϵ F and x ϵ V, then V is comparable to U; (iii) the intersection of k + 1 pairwise incomparable members of F is empty. The covering graphs of the 1-pseudotrees on an n-set (considered as posets under inclusion) are the directed rooted trees with n leaves and no vertex of outdegree one. It is shown that if k < n, then the maximum cardinality of a k-pseudotree on an n-element set is (k + 1)n − ((k + 1)k)/2.