TY - JOUR
T1 - Many T copies in H-free graphs
AU - Alon, Noga
AU - Shikhelman, Clara
N1 - Funding Information:
1 Sackler School of Mathematics and Blavatnik School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel and School of Mathematics, Institute for Advanced Study, Princeton, NJ 08540. Research supported in part by a USA-Israeli BSF grant, by an ISF grant, by the Israeli I-Core program and by the Oswald Veblen Fund. 2 Email: nogaa@tau.ac.il 3 Email: clarashk@mail.tau.ac.il
Publisher Copyright:
© 2015 Elsevier B.V.
PY - 2015/11
Y1 - 2015/11
N2 - For two graphs T and H with no isolated vertices and for an integer n, let ex(n, T, H) denote the maximum possible number of copies of T in an H-free graph on n vertices. The study of this function when T=K2 is a single edge is the main subject of extremal graph theory. In the present paper we investigate the general function, focusing on the cases of triangles, complete graphs, complete bipartite graphs and trees. These cases reveal several interesting phenomena. Three representative results are:(i)ex(n,K3,C5)≤(1+o(1))√3/2n3/2(ii)For any fixed m, s≥2m-2 and t≥(s-1)!+1, ex(n,Km,Ks,t)=Θ(nm-(m2)/s)(iii)For any two trees H and T one has ex(n, T, H)=Θ(nm) where m=m(T, H) is an integer depending on H and T (its precise definition is given in the introduction).The first result improves (slightly) an estimate of Bollobás and Gyori. The proofs combine combinatorial and probabilistic arguments with simple spectral techniques.
AB - For two graphs T and H with no isolated vertices and for an integer n, let ex(n, T, H) denote the maximum possible number of copies of T in an H-free graph on n vertices. The study of this function when T=K2 is a single edge is the main subject of extremal graph theory. In the present paper we investigate the general function, focusing on the cases of triangles, complete graphs, complete bipartite graphs and trees. These cases reveal several interesting phenomena. Three representative results are:(i)ex(n,K3,C5)≤(1+o(1))√3/2n3/2(ii)For any fixed m, s≥2m-2 and t≥(s-1)!+1, ex(n,Km,Ks,t)=Θ(nm-(m2)/s)(iii)For any two trees H and T one has ex(n, T, H)=Θ(nm) where m=m(T, H) is an integer depending on H and T (its precise definition is given in the introduction).The first result improves (slightly) an estimate of Bollobás and Gyori. The proofs combine combinatorial and probabilistic arguments with simple spectral techniques.
KW - Extremal Combinatorics
KW - Turán-type problems
UR - http://www.scopus.com/inward/record.url?scp=84947807649&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84947807649&partnerID=8YFLogxK
U2 - 10.1016/j.endm.2015.06.092
DO - 10.1016/j.endm.2015.06.092
M3 - Article
AN - SCOPUS:84947807649
SN - 1571-0653
VL - 49
SP - 683
EP - 689
JO - Electronic Notes in Discrete Mathematics
JF - Electronic Notes in Discrete Mathematics
ER -