The Minimum Number of Edges in Uniform Hypergraphs with Property O

Abstract

An oriented k-uniform hypergraph (a family of ordered k-sets) has the ordering property (or Property O) if for every linear order of the vertex set, there is some edge oriented consistently with the linear order. We find bounds on the minimum number of edges in a hypergraph with Property O.

9 pages, 1 figure