Partitioning ordered hypergraphs

Abstract An ordered r-graph is an r-uniform hypergraph whose vertex set is linearly ordered. Given 2 ≤ k ≤ r , an ordered r-graph H is interval k-partite if there exist at least k disjoint intervals in the ordering such that every edge of H has nonempty intersection with each of the intervals and is contained in their union. Our main result implies that if α > k − 1 , then for each d > 0 every n-vertex ordered r-graph with d n α edges has for some m ≤ n an m-vertex interval k-partite subgraph with Ω ( d m α ) edges. This is an extension to ordered r-graphs of the observation by Erdős and Kleitman that every r-graph contains an r-partite subgraph with a constant proportion of the edges. The restriction α > k − 1 is sharp. We also present applications of the main result to several extremal problems for ordered hypergraphs.