On non-degenerate Berge-Turán problems

Abstract: Given a hypergraph

m a t h c a l H

and a graph

G

, we say that

m a t h c a l H

is a extit{Berge}-

G

if there is a bijection between the hyperedges of

m a t h c a l H

and the edges of

G

such that each hyperedge contains its image. We denote by

e x_{k} (n, e x t B e r g e - F)

the largest number of hyperedges in a

k

-uniform Berge-

F

-free graph. Let

e x (n, H, F)

denote the largest number of copies of

H

in

n

-vertex

F

-free graphs. It is known that

e x (n, K_{k}, F) l e e x_{k} (n, e x t B e r g e - F) l e e x (n, K_{k}, F) + e x (n, F)

, thus if

c h i (F) > r

, then

e x_{k} (n, e x t B e r g e - F) = (1 + o (1)) e x (n, K_{k}, F)

. We conjecture that

e x_{k} (n, e x t B e r g e - F) = e x (n, K_{k}, F)

in this case. We prove this conjecture in several instances, including the cases

k = 3

and

k = 4

. We prove the general bound

e x_{k} (n, e x t B e r g e - F) = e x (n, K_{k}, F) + O (1)

.

Recommendations

Cites Work

Cited In (2)

This page was built for publication: On non-degenerate Berge-Turán problems