On a hypergraph Turán problem of Frankl

Abstract: Let

C_{r}^{2 k}

be the

2 k

-uniform hypergraph obtained by letting

P_{1}, ..., P_{r}

be pairwise disjoint sets of size

k

and taking as edges all sets

P_{i} c u p P_{j}

with

i e q j

. This can be thought of as the `

k

-expansion' of the complete graph

K_{r}

: each vertex has been replaced with a set of size

k

. We determine the exact Turan number of

C_{3}^{2 k}

and the corresponding extremal hypergraph, thus confirming a conjecture of Frankl. Sidorenko has given an upper bound of

(r - 2) / (r - 1)

for the Tur'an density of

C_{r}^{2 k}

for any

r

, and a construction establishing a matching lower bound when

r

is of the form

2^{p} + 1

. We show that when

r = 2^{p} + 1

, any

C_{r}^{4}

-free hypergraph of density

(r - 2) / (r - 1) - o (1)

looks approximately like Sidorenko's construction. On the other hand, when

r

is not of this form, we show that corresponding constructions do not exist and improve the upper bound on the Tur'an density of

C_{r}^{4}

to

(r - 2) / (r - 1) - c (r)

, where

c (r)

is a constant depending only on

r

. The backbone of our arguments is a strategy of first proving approximate structure theorems, and then showing that any imperfections in the structure must lead to a suboptimal configuration. The tools for its realisation draw on extremal graph theory, linear algebra, the Kruskal-Katona theorem and properties of Krawtchouck polynomials.

Recommendations

Cited in

(39)

This page was built for publication: On a hypergraph Turán problem of Frankl

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