The edge-density for minors

Let H be a graph. If G is an n-vertex simple graph that does not contain H as a minor, what is the maximum number of edges that G can have? This is at most linear in n, but the exact expression is known only for very few graphs H. For instance, when H is a complete graph K t , the “natural” conjecture, ( t − 2 ) n − 1 2 ( t − 1 ) ⋅ ( t − 2 ) , is true only for t ⩽ 7 and wildly false for large t, and this has rather dampened research in the area. Here we study the maximum number of edges when H is the complete bipartite graph K 2 , t . We show that in this case, the analogous “natural” conjecture, 1 2 ( t + 1 ) ( n − 1 ) , is (for all t ⩾ 2 ) the truth for infinitely many n.