Forbidden Berge Hypergraphs
| Autor: | Anstee, Richard, Salazar, Santiago |
|---|---|
| Rok vydání: | 2016 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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||\,:\, A \hbox{ is }m\hbox{-rowed simple matrix with no Berge hypergraph }F\}$. 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. Comment: 20 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|