The Turán number of the Cartesian product of graphs

2022/03/23 by Liu, Dingyuan
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2203.12503

Abstract

Recently, Domagoj Bradač, Oliver Janzer, Benny Sudakov and István Tomon have proved that the Turán number of 2-dimensional grids is Θ(n^3/2), or more general, ex(n,T\squareP)=Θ(n^3/2), where T is a non-trivial tree, P is a non-trivial path, and T\squareP denotes the Cartesian product. In their proof, they exhibited a novel way of using the tensor power trick, which has lots of potential in Turán type problems. By the end of their proof, they conjectured that ex(n,T\squareR)=Θ(n^3/2) for non-trivial trees T and R. This paper is an extension based on their work, we successfully prove the above conjecture by adapting their approach.

Related

• The Turán number of the grid
• The Turán number of the Cartesian product of trees via star-flip
• The Turán number of the square of a path
• The Turán number of k₁P_2l∪ k₂S_2l-1
• The Turan Number of Disjoint Copies of Paths