Partitioning ordered hypergraphs

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:177

Article

Furedi, Zoltan¹  Jiang, Tao²  Kostochka, Alexandr^3,4  Mubayi, Dhruv⁵  Verstraete, Jacques⁶ 

[1] Hungarian Acad Sci, Alfred Renyi Inst Math, Realtanoda Utca 13-15, H-1053 Budapest, Hungary

[2] Miami Univ, Dept Math, Oxford, OH 45056 USA

[3] Univ Illinois, Urbana, IL 61801 USA

[4] Sobolev Inst Math, Novosibirsk 630090, Russia

[5] Univ Illinois, Dept Math Stat & Comp Sci, Chicago, IL 60607 USA

[6] Univ Calif San Diego, Dept Math, 9500 Gilman Dr, La Jolla, CA 92093 USA

关键词: Turan problem;    Ordered hypergraphs;    Interval k-partite hypergraphs;   

DOI  :  10.1016/j.jcta.2020.105300

来源: Elsevier

【 摘 要 】

An ordered r-graphis an r-uniform hypergraph whose vertex set is linearly ordered. Given 2 <= k <= r, an ordered r-graph H is intervalk-partiteif there exist at least kdisjoint intervals in the ordering such that every edge of Hhas nonempty intersection with each of the intervals and is contained in their union. Our main result implies that if alpha > k - 1, then for each d > 0 every n-vertex ordered r-graph with dn(alpha) edges has for some m <= nan m-vertex interval k-partite subgraph with Omega(d m(alpha)) edges. This is an extension to ordered r-graphs of the observation by Erdos and Kleitman that every r-graph contains an r-partite subgraph with a constant proportion of the edges. The restriction alpha > k - 1 is sharp. We also present applications of the main result to several extremal problems for ordered hypergraphs. (C) 2020 Elsevier Inc. All rights reserved.

【 授权许可】

Free