Date:

Mon, 09/11/201511:00-13:00

Repeats every week every Monday until Mon Nov 23 2015

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

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