## 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 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.

Original language | English (US) |
---|---|

Article number | 105300 |

Journal | Journal of Combinatorial Theory. Series A |

Volume | 177 |

DOIs | |

State | Published - Jan 2021 |

## Keywords

- Interval k-partite hypergraphs
- Ordered hypergraphs
- Turán problem

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics