QUALITATIVE INDEPENDENCE AND SPERNER PROBLEMS FOR DIRECTED-GRAPHS

Sperner's theorem about the largest family of incomparable subsets of an n-set is in fact a theorem about the largest anti-chain in the natural extension to sequences of a linear order. We replace the linear order by an arbitrary directed graph and ask for the cardinality of the largest set of incomparable sequences of length n one can form of the vertices. Two sequences are comparable if for every coordinate, all the arcs between corresponding vertices (if any) go in the same direction. Similarly, we look for the largest cardinality of sets of sequences that are incomparable in any graph from a given family. We find the asymptotic solution in some cases and give constructions in others. Our results imply new lower bounds on the cardinality of the largest family of qualitatively two-independent partitions in the sense of Rényi. © 1992.