Saturation numbers for Berge cliques

Abstract: Let

F

be a graph and

m a t h c a l H

be a hypergraph, both embedded on the same vertex set. We say

m a t h c a l H

is a Berge-

F

if there exists a bijection

p h i : E (F) o E (m a t h c a l H)

such that

e s u b s e t e q p h i (e)

for all

e i n E (F)

. We say

m a t h c a l H

is Berge-

F

-saturated if

m a t h c a l H

does not contain any Berge-

F

, but adding any missing edge to

m a t h c a l H

creates a copy of a Berge-

F

. The saturation number

m a t h r m {s a t}_{k} (n, e x t B e r g e - F)

is the least number of edges in a Berge-

F

-saturated

k

-uniform hypergraph on

n

vertices. We show [ mathrm{sat}_k(n, ext{Berge-}K_ell)sim frac{ell-2}{k-1}n, ] for all

k, e l l g e q 3

. Furthermore, we provide some sufficient conditions to imply that

m a t h r m {s a t}_{k} (n, e x t B e r g e - F) = O (n)

for general graphs

F

.

Cites Work

This page was built for publication: Saturation numbers for Berge cliques