Forbidden Berge hypergraphs (Q521388)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Forbidden Berge hypergraphs |
scientific article |
Statements
Forbidden Berge hypergraphs (English)
0 references
10 April 2017
0 references
Summary: A 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 Berge hypergraph if there is a submatrix \(B\) of \(A\) and some row and column permutation of \(F\), say \(G\), with \(G\leq B\). Letting \(\|A\|\) denote the number of columns in \(A\), we define the extremal function \(\mathrm{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 \textit{N. Alon} and \textit{C. Shikhelman} [J. Comb. Theory, Ser. B 121, 146--172 (2016; Zbl 1348.05100)].
0 references
extremal graphs
0 references
Berge hypergraph
0 references
forbidden configuration
0 references
trace
0 references
products
0 references
0 references