Triangles in H-free graphs

Seminar
Speaker
Clara Shikhelman (Tel-Aviv University)
Date
23/11/2014 - 15:30 - 14:00Add to Calendar 2014-11-23 14:00:00 2014-11-23 15:30:00 Triangles in H-free graphs 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. אוניברסיטת בר-אילן - המחלקה למתמטיקה mathoffice@math.biu.ac.il Asia/Jerusalem public
Abstract

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.

תאריך עדכון אחרון : 18/11/2014