Triangles in H-free graphs

יום א', 23/11/2014 - 14:00

For two graphs T and H and 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 = K_2 (a single edge) is one of the main subjects of extremal graph theory. We investigate the general function, focusing on the case T = K_3, which reveals several interesting phenomena.

In this talk we will present proofs of the following main results:
(i) For any fixed s > 1 and t > (s-1) one has ex(n,K_3,K_{s,t})=\Theta(n^{3-3/s}), and
(ii) ex(n,K_3,C_5) < (1+o(1)) (\sqrt 3)/2 n^{3/2}.

The last statement improves (slightly) a result of Bollobas and Gyori.

Joint work with Noga Alon.