A polynomial resultant approach to algebraic constructions of extremal graphs

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 \(K_{3,t_{1}}\) $$K_{3,t_1}$$ and the linear Turán number of the Berge theta hypergraph \(\Theta_{3,t_{2}}^{B}\) $${\mathrm{\Theta }}_{3,t_2}^B$$ , where t₁ = 25 and t₂ = 217. Moreover, the constant t₁ improves the random algebraic construction of Bukh and Conlon (2018) and makes the known estimation better on the smallest value of t₁ concerning a problem posed by Conlon et al. (2021) by reducing the value from a magnitude of 10⁵⁶ to the number 25, while the constant t₂ improves a result of He and Tait (2019).