TY - JOUR

T1 - The edge-density for K2,t minors

AU - Chudnovsky, Maria

AU - Reed, Bruce

AU - Seymour, Paul

N1 - Funding Information:
E-mail address: pds@math.Princeton.edu (P. Seymour). 1 This research was conducted while the author served as a Clay Mathematics Institute Research Fellow. 2 Supported by ONR grant N00014-01-1-0608 and NSF grant DMS-0070912.

PY - 2011/1

Y1 - 2011/1

N2 - 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 Kt, 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 K2,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.

AB - 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 Kt, 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 K2,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.

KW - Extremal

KW - Graph

KW - Minors

UR - http://www.scopus.com/inward/record.url?scp=78249273933&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=78249273933&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2010.09.001

DO - 10.1016/j.jctb.2010.09.001

M3 - Article

AN - SCOPUS:78249273933

VL - 101

SP - 18

EP - 46

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

SN - 0095-8956

IS - 1

ER -