A polynomial resultant approach to algebraic constructions of extremal graphs

Abstract

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 polynomail resultant approach to 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 lowers bounds for Turán number of $1$-subdivision of $K_{3,t_1}$ and linear Turán number of Berge theta hyerpgraph ${\Theta }_{3,t_2}^B$ with $t_1=25$ and $t_2=217$. Moreover, the constant $t_1$ improves the random algebraic construction of Bukh and Conlon~[Rational exponents in extremal graph theory, J. Eur. Math. Soc. 20 (2018), 1747-1757] and makes progress on the known estimation for the smallest value of $t_1$ concerning a problem posed by Conlon, Janzer and Lee ~[More on the extremal number of subdivisions, Combinatorica, to appear], while the constant $t_2$ improves a result of He and Tait~[Hypergraphs with few berge paths of fixed length between vertices, SIAM J. Discrete Math., 33(3), 1472-1481].

arXiv comment46 pages. arXiv admin note: substantial text overlap with arXiv:2002.06795, arXiv:1908.01459

References in corpus (3)

• Graphs with few paths of prescribed length between any two vertices
• Turán numbers for $K_{s,t}$-free graphs: topological obstructions and algebraic constructions
• Some tight lower bounds for Turán problems via constructions of multi-hypergraphs