Speaker: Lior Gishboliner, Tel Aviv University

Title: A Generalized Turan Problem and Its Applications

Abstract:

The investigation of conditions guaranteeing the appearance of cycles

of certain lengths is one of the most well-studied topics in graph

theory. In this paper we consider a problem of this type which asks,

for fixed integers ℓ and k, how many copies of the k-cycle guarantee

the appearance of an ℓ-cycle? Extending previous results of

Bollobas-Gyori-Li and Alon-Shikhelman, we fully resolve this problem

by giving tight (or nearly tight) bounds for all values of ℓ and k.

We also present a somewhat surprising application of the above mentioned

estimates to the study of the graph removal lemma. Prior to this work,

all bounds for removal lemmas were either polynomial or there was a

tower-type gap between the best known upper and lower bounds. We fill

this gap by showing that for every super-polynomial function f(ε), there

is a family of graphs F, such that the bounds for the F removal lemma

are precisely given by f(ε). We thus obtain the first examples of

removal lemmas with tight super-polynomial bounds. A special case of

this result resolves a problem of Alon-Shapira, while another special

case partially resolves a problem of Goldreich.

Joint work with Asaf Shapira

Title: A Generalized Turan Problem and Its Applications

Abstract:

The investigation of conditions guaranteeing the appearance of cycles

of certain lengths is one of the most well-studied topics in graph

theory. In this paper we consider a problem of this type which asks,

for fixed integers ℓ and k, how many copies of the k-cycle guarantee

the appearance of an ℓ-cycle? Extending previous results of

Bollobas-Gyori-Li and Alon-Shikhelman, we fully resolve this problem

by giving tight (or nearly tight) bounds for all values of ℓ and k.

We also present a somewhat surprising application of the above mentioned

estimates to the study of the graph removal lemma. Prior to this work,

all bounds for removal lemmas were either polynomial or there was a

tower-type gap between the best known upper and lower bounds. We fill

this gap by showing that for every super-polynomial function f(ε), there

is a family of graphs F, such that the bounds for the F removal lemma

are precisely given by f(ε). We thus obtain the first examples of

removal lemmas with tight super-polynomial bounds. A special case of

this result resolves a problem of Alon-Shapira, while another special

case partially resolves a problem of Goldreich.

Joint work with Asaf Shapira

## Date:

Mon, 04/06/2018 - 11:00 to 12:30

## Location:

IIAS, room 130, Feldman Building, Givat Ram