Directed graphs as unions of partial orders

Peter C. Fishburn, Joel H. Spencer

Research output: Contribution to journalArticle

Abstract

The index of an irreflexive binary relation R is the smallest cardinal number σ(R) such that R equals the union of σ(R) partial orders. With s(n) the largest index for an R defined on n points, it is shown that s(n)/log2 n→1 as n →∞. The index function is examined for symmetric R’s and almost transitive R’s, and a characterization for σ(R)≦2 is presented. It is shown also that inf{n:s(n)>3}≦13, but the exact value of inf {n:s(n)>3} is presently unknown.

Original languageEnglish (US)
Pages (from-to)149-161
Number of pages13
JournalPacific Journal of Mathematics
Volume39
Issue number1
DOIs
StatePublished - Oct 1971

    Fingerprint

ASJC Scopus subject areas

  • Mathematics(all)

Cite this