Combinatorics Seminar

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

w3c valid   accessible website
redesigned by barak soreq