Property O and Erdős–Szekeres properties in linear hypergraphs

An oriented k -uniform hypergraph, or oriented k -graph, is said to satisfy Property O if, for every linear ordering of its vertex set, there is some edge oriented consistently with this order. The minimum number f ( k ) of edges in a k -graph with Property O was first studied by Duffus, Kay, and Rödl; the bounds were later improved by Kronenberg, Kusch, Lamaison, Micek, and Tran. In particular, they established the bounds k ! + 1 ⩽ f ( k ) ⩽ ( ⌊ k 2 ⌋ + 1 ) k ! − ⌊ k 2 ⌋ ( k − 1 ) ! for every k ⩾ 2 . In this note, we extend the study of Property O to the linear setting. We determine the minimum number f ′ ( k ) of edges in an oriented linear k -graph with Property O up to a poly ( k ) multiplicative factor, showing that ( k ! ) 2 2 e 2 k 4 ⩽ f ′ ( k ) ⩽ ( 1 + o ( 1 ) ) ⋅ 4 k 6 ln 2 ⁡ k ⋅ ( k ! ) 2 . Our approach also yields bounds on the minimum number n ′ ( k ) of vertices in an oriented linear k -graph with Property O. Additionally, we explore the minimum number of edges and vertices required in a linear k -graph satisfying the newly introduced Erdős–Szekeres properties.