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.
אוניברסיטת בר-אילן - Department of Mathematics
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.
Last Updated Date : 18/11/2014
