A polynomial resultant approach to algebraic constructions of extremal graphs
作者机构：Institute of Mathematics and Interdisciplinary Sciences Xidian University School of Mathematical Sciences Capital Normal University
出 版 物：《Science China Mathematics》 (中国科学:数学(英文版))
年 卷 期：2024年
核心收录：
学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学]
基 金：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 Turan 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 Turan number of 1-subdivision of K3,t1and the linear Turan number of the Berge theta hypergraphΘ3B,t2, where t1= 25 and t2= 217. Moreover, the constant t1 improves the random algebraic construction of Bukh and Conlon（2018） and makes the known estimation better on the smallest value of t1 concerning a problem posed by Conlon et al.（2021） by reducing the value from a magnitude of 1056 to the number 25, while the constant t2improves a result of He and Tait（2019）.
同方期刊数据库