MATH Seminar

Title: Turan's problem for odd cycles in pseudorandom graphs
Seminar: Combinatorics
Speaker: Mathias Schacht of University of Hamburg
Contact: Dwight Duffus, dwight@mathcs.emory.edu
Date: 2011-10-07 at 4:00PM
Venue: W306
Download Flyer
Abstract: We consider the generalized extremal function $ex(G,F)$, defined to be the largest number of edges that an $F$-free subgraph of $G$ may have. Owing to the work of Mantel, Turan, Erd\"os and Stone this function is well understood for any graph F when $G$ is the complete graph $K_n$. Over the last two decades the problem was investigated and solved when $G$ is the binomial random graph {\bf G(n,p)}. For pseudorandom graphs $G$ only a few results are known. We will discuss recent progress for one of the simplest cases, when F is an odd cycle of fixed length. Roughly speaking, in joint work with Aigner-Horev and Han we obtained almost best possible conditions on the pseudorandom graph $G$ such that $ex(G,C_l)=(1/2+o(1)e(G)$ holds.