Forbidden Berge hypergraphs

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Abstract: A emph{simple} matrix is a (0,1)-matrix with no repeated columns. For a (0,1)-matrix

F

, we say that a (0,1)-matrix

A

has

F

as a emph{Berge hypergraph} if there is a submatrix

B

of

A

and some row and column permutation of

F

, say

G

, with

G l e B

. Letting

| | A | |

denote the number of columns in

A

, we define the extremal function

B h (m, F) = m a x | | A | |, :, A h b o x i s m h b o x - r o w e d s i m p l e m a t r i x w i t h n o B e r g e h y p e r g r a p h F

. We determine the asymptotics of

B h (m, F)

for all

3

- and

4

-rowed

F

and most

5

-rowed

F

. For certain

F

, this becomes the problem of determining the maximum number of copies of

K_{r}

in a

m

-vertex graph that has no

K_{s, t}

subgraph, a problem studied by Alon and Shinkleman.

Recommendations

Cites work

Cited in

(8)

This page was built for publication: Forbidden Berge hypergraphs