2019/06/07 by Zoltán F uredi, Tao Jiang, uredi, Zoltán F\" +7
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1906.03342
openalex publication_date 2019/06/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An \em ordered r-graph is an r-uniform hypergraph whose vertex set is linearly ordered. Given 2≤ k≤ r, an ordered r-graph H is \em interval k-\em 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 for each α> k - 1 and 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\H os 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.