When: Sunday, April 26, 10am
Where: Schreiber 309
Speaker: Clara Shikhelman, Tel Aviv U.
Title: Many T copies in H-free graphs
For two graphs T and H 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=K_2 (a single edge) is the main subject of extremal graph theory. We investigate the general function, focusing on the cases of triangles, complete graphs and trees.
In this talk the main results will be presented as will sketches of proofs of some of the following:
(i) ex(n,K_3,C_5) < (1+o(1)) (\sqrt 3)/2 n^{3/2}.
(ii) For any fixed integer m, s > 2m-3 and t >(s-1)!, ex(n,K_m,K_{s,t})=\Theta(n^{m-m(m-1)/2s}), and
(iii) For any two trees H and T there are two constants c_1 and c_2 for which c_1 n^m< ex(n,T,H) < c_2 n^m, where m=m(T,H) is an integer depending on H and T.
The first statement improves (slightly) a result of Bollobas and Gyori.
Joint work with Noga Alon
