错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On Non-degenerate Berge–Turán Problems

  • Dániel Gerbner

摘要

Given a hypergraph \({{\mathcal {H}}}\) H and a graph G, we say that \({{\mathcal {H}}}\) H is a Berge-G if there is a bijection between the hyperedges of \({{\mathcal {H}}}\) H and the edges of G such that each hyperedge contains its image. We denote by \(\textrm{ex}_k(n,Berge- F)\) ex k ( n , B e r g e - F ) the largest number of hyperedges in a k-uniform Berge-F-free graph. Let \(\textrm{ex}(n,H,F)\) ex ( n , H , F ) denote the largest number of copies of H in n-vertex F-free graphs. It is known that \(\textrm{ex}(n,K_k,F)\le \textrm{ex}_k(n,Berge- F)\le \textrm{ex}(n,K_k,F)+\textrm{ex}(n,F)\) ex ( n , K k , F ) ex k ( n , B e r g e - F ) ex ( n , K k , F ) + ex ( n , F ) , thus if \(\chi (F)>r\) χ ( F ) > r , then \(\textrm{ex}_k(n,Berge- F)=(1+o(1)) \textrm{ex}(n,K_k,F)\) ex k ( n , B e r g e - F ) = ( 1 + o ( 1 ) ) ex ( n , K k , F ) . We conjecture that \(\textrm{ex}_k(n,Berge- F)=\textrm{ex}(n,K_k,F)\) ex k ( n , B e r g e - F ) = ex ( n , K k , F ) in this case. We prove this conjecture in several instances, including the cases \(k=3\) k = 3 and \(k=4\) k = 4 . We prove the general bound \(\textrm{ex}_k(n,Berge- F)= \textrm{ex}(n,K_k,F)+O(1)\) ex k ( n , B e r g e - F ) = ex ( n , K k , F ) + O ( 1 ) .