Extremal Problems for Hypergraph Blowups of Trees

DOI10.1137/22M1543318MaRDI QIDQ6057807zbMATH OpenOpenAlexFDO

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

Publication date 26 October 2023

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2003.00622

\(\Delta\)-systems extremal hypergraph theory hypergraph trees

Trees (05C05) Enumeration in graph theory (05C30) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Hypergraphs (05C65)

Abstract: In this paper we present a novel approach in extremal set theory which may be viewed as an asymmetric version of Katona's permutation method. We use it to find more Tur'an numbers of hypergraphs in the ErdH{o}s--Ko--Rado range. An

(a, b)

-path

P

of length

2 k - 1

consists of

2 k - 1

sets of size

r = a + b

as follows. Take

k

pairwise disjoint

a

-element sets

A_{0}, A_{2}, d o t s, A_{2 k - 2}

and other

k

pairwise disjoint

b

-element sets

B_{1}, B_{3}, d o t s, B_{2 k - 1}

and order them linearly as

A_{0}, B_{1}, A_{2}, B_{3}, A_{4} d o t s

. Define the (hyper)edges of

P_{2 k - 1} (a, b)

as the sets of the form

A_{i} c u p B_{i + 1}

and

B_{j} c u p A_{j + 1}

. The members of

P

can be represented as

r

-element intervals of the

a k + b k

element underlying set. Our main result is about hypergraphs that are blowups of trees, and implies that for fixed

k, a, b

, as

n o i n f t y

[ { m ex}_r(n,P_{2k-1}(a,b)) = (k - 1){n choose r - 1} + o(n^{r - 1}).] This generalizes the ErdH{o}s--Gallai theorem for graphs which is the case of

a = b = 1

. We also determine the asymptotics when

a + b

is even; the remaining cases are still open.

Recommendations

Cites work

Cited in

(2)

This page was built for publication: Extremal Problems for Hypergraph Blowups of Trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6057807)