## Combinatorics Seminar

When: Sunday, March 4, 10am

Where: Schreiber 309

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
and the second author, while another special case partially resolves a problem
of Goldreich.

Joint
work with Asaf Shapira