EXTREMAL PROBLEMS FOR HYPERGRAPH BLOWUPS OF TREES

Zoltan Furedi, Tao Jiang, Alexandr Kostochka, Dhruv Mubayi, Jacques Verstraete

Research output: Contribution to journalArticlepeer-review

Abstract

We study the extremal number for paths in r-uniform hypergraphs where two consecutive 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.

Original languageEnglish (US)
Pages (from-to)2397-2416
Number of pages20
JournalSIAM Journal on Discrete Mathematics
Volume37
Issue number4
DOIs
StatePublished - 2023

Keywords

  • \Delta-systems
  • extremal hypergraph theory
  • hypergraph trees

ASJC Scopus subject areas

  • General Mathematics

Fingerprint

Dive into the research topics of 'EXTREMAL PROBLEMS FOR HYPERGRAPH BLOWUPS OF TREES'. Together they form a unique fingerprint.

Cite this