Partitioning ordered hypergraphs

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 dn^α edges has for some m≤n an m-vertex interval k-partite subgraph with Ω(dm^α) 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.