Forbidden Berge Hypergraphs

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\le B$. Letting $||A||$ denote the number of columns in $A$, we define the extremal function $Bh(m,F)=\max \{||A||:Aism-rowed\; simple\; matrix\; with\; no\; Berge\; hypergraphF\}$. We determine the asymptotics of $Bh(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.

20 pages