A Note on the Minimum Number of Edges in Hypergraphs with Property O

Abstract

An oriented $k$-uniform hypergraph is said to have Property O if for every linear order of the vertex set, there is some edge oriented consistently with the linear order. Recently Duffus, Kay and Rödl investigated the minimum number $f(k)$ of edges in a $k$-uniform hypergaph with Property O. They proved that $k!\le f(k)\le (k^2\ln k)k!$, where the upper bound holds for $k$ sufficiently large. In this short note we improve their upper bound by a factor of $k\ln k$, showing that $f(k)\le \left(\lfloor \frac{k}{2}\rfloor +1\right)k!-\lfloor \frac{k}{2}\rfloor (k-1)!$ for every $k\ge 3$. We also show that their lower bound is not tight. Furthermore, Duffus, Kay and Rödl also studied the minimum number $n(k)$ of vertices in a $k$-uniform hypergaph with Property O. For $k=3$ they showed $n(3)\in \{6,7,8,9\}$, and asked for the precise value of $n(3)$. Here we show $n(3)=6$.

6 pages, 1 figure