2015/02/09 by Jiang, Tao, Newman, Andrew · 1 citation
#05C35 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1502.02602
Given a family \cal F of graphs, and a positive integer n, the Turán number ex(n,\cal F) of \cal F is the maximum number of edges in an n-vertex graph that does not contain any member of \cal F as a subgraph. The order of a graph is the number of vertices in it. In this paper, we study the Turán number of the family of graphs with bounded order and high average degree. For every real d≥ 2 and positive integer m≥ 2, let \cal Fd,m denote the family of graphs on at most m vertices that have average degree at least d. It follows from the Erdős-Rényi bound that ex(n,\cal Fd,m)=Ω(n2-(2)/(d)+(c)/(dm)), for some positive constant c. Verstraëte asked if it is true that for each fixed d there exists a function εd(m) that tends to 0 as m→ ∞ such that ex(n,\cal Fd,m)=O(n2-(2)/(d)+εd(m)). We answer Verstraëte's question in the affirmative whenever d is an integer. We also prove an extension of the cube theorem on the Turán number of the cube Q3, which partially answers a question of Pinchasi and Sharir.