Let F be a graph and H be a hypergraph.We say that H contains a Berge-F If there exists a bijectionψ:E(F)→E(H)such that for Ve E E(F),e C(e),and the Turan number of Berge-F is defined to be the maximum number of edg...Let F be a graph and H be a hypergraph.We say that H contains a Berge-F If there exists a bijectionψ:E(F)→E(H)such that for Ve E E(F),e C(e),and the Turan number of Berge-F is defined to be the maximum number of edges in an r-uniform hypergraph of order n that is Berge-F-free,denoted by ex,(n,Berge-F).A linear forest is a graph whose connected components are all paths or isolated vertices.Let Ln,k be the family of all linear forests of n vertices with k edges.In this paper,Turan number of Berge-Ln,in an r-uniform hypergraph is studied.When r≥k+1 and 3≤r≤l[]=1,we determine 2 the exact value of ex,(n,Berge-Ln,)respectively.When K-1≤r≤k,we 2 determine the upper bound of ex,(n,Berge-Ln,).展开更多
The Turán problem asks for the largest number of edges ex(n,H)in an n-vertex graph not containing a fixed forbidden subgraph H,which is one of the most important problems in extremal graph theory.However,the orde...The Turán problem asks for the largest number of edges ex(n,H)in an n-vertex graph not containing a fixed forbidden subgraph H,which is one of the most important problems in extremal graph theory.However,the order of magnitude of ex(n,H)for bipartite graphs is known only in a handful of cases.In particular,giving explicit constructions of extremal graphs is very challenging in this field.In this paper,we develop a polynomial resultant approach to the algebraic construction of explicit extremal graphs,which can efficiently decide whether a specified structure exists.A key insight in our approach is the multipolynomial resultant,which is a fundamental tool of computational algebraic geometry.Our main results include the matched lower bounds on the Turán number of 1-subdivision of K3,t1and the linear Turán number of the Berge theta hypergraph■_(3,t_(2))^(B).where t_(1)=25 and t_(2)=217.Moreover,the constant t1improves the random algebraic construction of Bukh and Conlon(2018)and makes the known estimation better on the smallest value of t1concerning a problem posed by Conlon et al.(2021)by reducing the value from a magnitude of 10^(56)to the number 25,while the constant t_(2)improves a result of He and Tait(2019).展开更多
文摘Let F be a graph and H be a hypergraph.We say that H contains a Berge-F If there exists a bijectionψ:E(F)→E(H)such that for Ve E E(F),e C(e),and the Turan number of Berge-F is defined to be the maximum number of edges in an r-uniform hypergraph of order n that is Berge-F-free,denoted by ex,(n,Berge-F).A linear forest is a graph whose connected components are all paths or isolated vertices.Let Ln,k be the family of all linear forests of n vertices with k edges.In this paper,Turan number of Berge-Ln,in an r-uniform hypergraph is studied.When r≥k+1 and 3≤r≤l[]=1,we determine 2 the exact value of ex,(n,Berge-Ln,)respectively.When K-1≤r≤k,we 2 determine the upper bound of ex,(n,Berge-Ln,).
基金supported by the Institute for Basic Science(IBS-R029-C4)supported by the National Key Research and Development Program of China(Grant No.2020YFA0712100)+1 种基金National Natural Science Foundation of China(Grant No.12231014)Beijing Scholars Program。
文摘The Turán problem asks for the largest number of edges ex(n,H)in an n-vertex graph not containing a fixed forbidden subgraph H,which is one of the most important problems in extremal graph theory.However,the order of magnitude of ex(n,H)for bipartite graphs is known only in a handful of cases.In particular,giving explicit constructions of extremal graphs is very challenging in this field.In this paper,we develop a polynomial resultant approach to the algebraic construction of explicit extremal graphs,which can efficiently decide whether a specified structure exists.A key insight in our approach is the multipolynomial resultant,which is a fundamental tool of computational algebraic geometry.Our main results include the matched lower bounds on the Turán number of 1-subdivision of K3,t1and the linear Turán number of the Berge theta hypergraph■_(3,t_(2))^(B).where t_(1)=25 and t_(2)=217.Moreover,the constant t1improves the random algebraic construction of Bukh and Conlon(2018)and makes the known estimation better on the smallest value of t1concerning a problem posed by Conlon et al.(2021)by reducing the value from a magnitude of 10^(56)to the number 25,while the constant t_(2)improves a result of He and Tait(2019).
