2025/09/10 by Suyun Jiang, Jiang, Suyun, Ander Lamaison +3
Computer Science · Mathematics · #05C35 #05C65 (Primary) #05D40 (Secondary) #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2509.08692
openalex publication_date 2025/09/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 ≤ f(k) ≤ (\lfloor\tfrack2\rfloor+1 ) k! - \lfloor\tfrack2\rfloor(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 a linear k-graph up to a poly(k) multiplicative factor, showing that ((k!)2)/(2e2k4) ≤ f'(k) ≤ (1+o(1)) ⋅ 4 k6 ln2 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.