# Combinatorics Seminar

When: Sunday, April 26, 10am

Where: Schreiber 309

Speaker: Clara Shikhelman, Tel Aviv U.

Title: Many T copies in H-free graphs

## Abstract:

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

redesigned by barak soreq