2014/04/04 by Noga Alon, Alon, Noga, Raphael Yuster +1 · 1 citation
Mathematics · #05C35 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C35
paper · pdf · doi:10.48550/arxiv.1404.1182
arxiv created 2014/04/04 · arxiv updated 2014/04/07
For a graph H, the \em extremal number ex(n,H) is the maximum number of edges in a graph of order n not containing a subgraph isomorphic to H. Let δ(H)>0 and Δ(H) denote the minimum degree and maximum degree of H, respectively. We prove that for all n sufficiently large, if H is any graph of order n with Δ(H) ≤ √(n)/200, then ex(n,H)=n-1 \choose 2+δ(H)-1. The condition on the maximum degree is tight up to a constant factor. This generalizes a classical result of Ore for the case H=Cn, and resolves, in a strong form, a conjecture of Glebov, Person, and Weps for the case of graphs. A counter-example to their more general conjecture concerning the extremal number of bounded degree spanning hypergraphs is also given.