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

Abstract

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, and later improved by Kronenberg, Kusch, Lamaison, Micek, and Tran. In particular, they established the bounds $k!+1\le f(k)\le \left(\lfloor \frac{k}{2}\rfloor +1\right)k!-\lfloor \frac{k}{2}\rfloor (k-1)!$ for every $k\ge 2$. In this note, we extend the study of Property O to the linear setting. We determine the minimum number $f^{\prime }(k)$ of edges in a linear $k$-graph up to a $\mathrm{poly}(k)$ multiplicative factor, showing that $\frac{(k!{)}^2}{2e^2{k}^4}\le f^{\prime }(k)\le (1+o(1))\cdot 4k^6{\ln }^{2}k\cdot (k!{)}^2$. Our approach also yields bounds on the minimum number $n^{\prime }(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.

10 pages