A note on the minimum number of edges in hypergraphs with property O

摘要

An oriented k-graph 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 Rod' investigated the minimum number f(k) of edges in a k-uniform hypergraph with Property O. They proved that k! <= f (k) <= (k(2) ln k)k!, where the upper bound holds for sufficiently large k. In this short note we improve their upper bound by a factor of k ln k showing that f (k) <= (left perpendiculark/2right perpendicular + 1) k! - left perpendiculark/2right perpendicular (k - 1)! for every k >= 3. We also show that their lower bound is not tight. Furthermore, Duffus, Kay and Rodl also studied the minimum possible number n(k) of vertices in an oriented k-graph with Property O. For k = 3 they showed that n(3) is an element of {6, 7, 8, 9}, and asked for the precise value of n(3). Here we show that n(3) = 6. (C) 2019 Elsevier Ltd. All rights reserved.