Extremal Problems for Hypergraph Blowups of Trees

Füredi, Zoltán and Jiang, T. and Kostochka, A. and Mubayi, D. and Verstraete, J. (2023) Extremal Problems for Hypergraph Blowups of Trees. SIAM JOURNAL ON DISCRETE MATHEMATICS, 37 (4). pp. 2397-2416. ISSN 0895-4801

Preview

Text 22m1543318.pdf Available under License Creative Commons Attribution. Download (437kB) | Preview

Abstract

We study the extremal number for paths in r-uniform hypergraphs where two consec- utive edges of the path intersect alternately in sets of sizes b and a with a + b = r and all other pairs of edges have empty intersection. Our main result, which is about hypergraphs that are blowups of trees, determines asymptotically the extremal number of these (a, b)-paths that have an odd number of edges or that have an even number of edges and a > b. This generalizes the Erd\H os--Gallai theorem for graphs, which is the case of a = b = 1. Our proof method involves a novel twist on Katona's permutation method, where we partition the underlying hypergraph into two parts, one of which is very small. We also find the asymptotics of the extremal number for the (1, 2)-path of length 4 using the different \Delta -systems method.

Actions (login required)

Edit Item