Combinatorics seminar

Date: 
Location: 
B221 Rothberg (CS and Engineering building)
Speaker: Clara Shikhelman, TAU
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 one has c_1 n^m integer depending on H and T.
The first statement improves (slightly) a result of Bollobas and
Gyori.
Joint work with Noga Alon