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.

Review text

Let \({\mathcal C}^{(2k)}_r\) be the hypergraph on the pairwise disjoint \(k\)-sets \(P_1,\dots,P_r\) consisting of the edges \(P_i\cup P_j\) (\(i\neq j\)). Let \({\mathcal B}^{(2k)}_n\) be a \(2k\)-uniform hypergraph on \(n\) vertices allowing a partition \(V=V_1\cup V_2\) of the vertices such that all edges intersect \(V_1\) in an odd number of elements and \({\mathcal B}^{(2k)}_n\) has the maximal number of edges. It is proved that, for \(n\) large, if a \(2k\)-hypergraph on \(n\) vertices omits \({\mathcal C}^{(2k)}_3\) then it has at most as many edges as \({\mathcal B}^{(2k)}_n\) (a conjecture of Frankl). Sidorenko showed that the Turán density of a \({\mathcal C}^{(2k)}_r\)-free hypergraph is at most \(\frac{r-2}{r-1}\) and gave a construction for a matching lower bound for \(r\) of the form \(2^p+1\). The authors show that if \(r=2^p+1\) then every \({\mathcal C}^{(4)}_r\)-free hypergraph with density \(\frac{r-2}{r-1}-o(1)\) approaches Sidorenko's construction. If, however, \(r\) is not of this form, then a better upper bound (for \({\mathcal C}^{(4)}_r\)) \(\frac{r-2}{r-1}-\varepsilon_r\) is given with some \(\varepsilon_r>0\).

Recommendations

Cited in

(43)

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)