On an extremal hypergraph problem related to combinatorial batch codes

. This problem is related to the forbidden hypergraph problem introduced by Brown, ErdH{o}s, and S'os and very recently discussed in the context of combinatorial batch codes. In this short paper we obtain the following results. {enumerate}[(i)] Using a result due to ErdH{o}s we are able to show

m (n, k, r) = o (n^{r})

for

7 l e q k

, and

3 l e q r l e q k - 1 - l c e i l l o g k c e i l

. This result is best possible with respect to the upper bound on

r

as we subsequently show through explicit construction that for

6 l e q k

, and

k - l c e i l l o g k c e i l l e q r l e q k - 1, m (n, r, k) = T h e t a (n^{r})

. This explicit construction improves on the non-constructive general lower bound obtained by Brown, ErdH{o}s, and S'os for the considered parameter values. For 2-uniform CBCs we obtain the following results. {enumerate} We provide exact value of

m (n, 2, 5)

for

n g e q 5

. Using a result of Lazebnik,et al. regarding maximum size of graphs with large girth, we improve the existing lower bound on

m (n, 2, k)

(

O m e g a (n^{f r a c k + 1 k - 1})

) for all

k g e q 8

and infinitely many values of

n

. We show

m (n, 2, k) = O (n^{1 + f r a c 1 l f l o o r f r a c k 4 f l o o r})

by using a result due to Bondy and Simonovits, and also show

m (n, 2, k) = T h e t a (n^{3 / 2})

for

k = 6, 7, 8

by using a result of K"{o}vari, S'os, and Tur'{a}n.

Recommendations

Cites work

Cited in

(7)

This page was built for publication: On an extremal hypergraph problem related to combinatorial batch codes

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