A polynomial resultant approach to algebraic constructions of extremal graphs  

作　　者：Tao Zhang Zixiang Xu Gennian Ge 

机构地区：[1]Institute of Mathematics and Interdisciplinary Sciences,Xidian University,Xi’an 710071,China [2]School of Mathematical Sciences,Capital Normal University,Beijing 100048,China

出　　处：《Science China Mathematics》2025年第2期485-506,共22页中国科学(数学英文版)

基　　金：supported by the Institute for Basic Science(IBS-R029-C4);supported by the National Key Research and Development Program of China(Grant No.2020YFA0712100);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).

关 键 词：Turan number RESULTANT algebraic construction SUBDIVISION Berge theta hypergraph 

分 类 号：O157.5[理学—数学]