Many T copies in H-free graphs

Noga Alon, Clara Shikhelman

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)683-689
Number of pages7
JournalElectronic Notes in Discrete Mathematics
Volume49
DOIs
StatePublished - Nov 2015
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Keywords

  • Extremal Combinatorics
  • Turán-type problems

Fingerprint Dive into the research topics of 'Many T copies in H-free graphs'. Together they form a unique fingerprint.

Cite this