Partitioning ordered hypergraphs

Zoltán Füredi, Tao Jiang, Alexandr Kostochka, Dhruv Mubayi, Jacques Verstraëte

Research output: Contribution to journalArticlepeer-review


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 languageEnglish (US)
Article number105300
JournalJournal of Combinatorial Theory. Series A
StatePublished - Jan 2021


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

ASJC Scopus subject areas

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


Dive into the research topics of 'Partitioning ordered hypergraphs'. Together they form a unique fingerprint.

Cite this