Forbidden Berge hypergraphs

MaRDI QIDQ521388zbMATH OpenFDO

Authors R. P. Anstee, Santiago Salazar

Publication date 10 April 2017

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1608.03632, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p59

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

zbMATH Keywords

Berge hypergraphextremal graphsforbidden configurationproductstrace

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Hypergraphs (05C65)

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 $GleB$. Letting $||A||$ denote the number of columns in $A$, we define the extremal function $Bh(m,F)=max||A||,:,Ahboxismhbox-rowedsimplematrixwithnoBergehypergraphF$. 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.

Review text

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)].

Recommendations

• Forbidden submatrices: some new bounds and constructions
• Forbidden families of configurations
• Extremal results for Berge hypergraphs
• Forbidden configurations: boundary cases
• Small forbidden configurations

Cites work

• A survey of forbidden configuration results
• An Upper Bound on Zarankiewicz' Problem
• Davenport-Schinzel theory of matrices
• Excluded permutation matrices and the Stanley-Wilf conjecture
• Extremal results for Berge hypergraphs
• Forbidden configurations and product constructions
• Forbidden families of configurations
• Forbidden submatrices
• scientific article; zbMATH DE number 3285073 (Why is no real title available?)
• Many \(T\) copies in \(H\)-free graphs
• On a problem of K. Zarankiewicz
• On extremal problems of graphs and generalized graphs
• On Graphs that do not Contain a Thomsen Graph
• On the structure of linear graphs
• Small forbidden configurations. IV: The 3 rowed case
• Turán Problems and Shadows III: Expansions of Graphs
• Two refinements of the bound of Sauer, Perles and Shelah, and of Vapnik and Chervonenkis
• Unavoidable traces of set systems

Cited in

(8)

• Forbidden submatrices: some new bounds and constructions
• Hypergraph based Berge hypergraphs
• Turán numbers for hypergraph star forests
• Ramsey numbers of Berge-hypergraphs and related structures
• Avoiding long Berge cycles
• Asymptotics for the Turán number of Berge-\(K_{2,t}\)
• On the weight of Berge-\(F\)-free hypergraphs
• Forbidden configurations for hypohamiltonian graphs

This page was built for publication: Forbidden Berge hypergraphs

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