Zoltan Furedi: Zykov’s symmetrization for multiple graphs, a new tool for Turán type problems with an application to Erdős’ conjecture on pentagonal edges

Erdős, Faudree, and Rousseau (1992) showed that a graph on n vertices with [n²/4]+1 edges has at least 2[n/2]+1 edges on triangles and this result is sharp.

They also showed that such a graph has at least cn² pentagonal edges and conjectured that an extremal graph has two components, a complete graph on [2n/3] + 1 vertices and a complete bipartite graph on the rest.

In this talk we give a graph of [n²/4] + 1 edges with much fewer, namely n²(2+√2)/16 + O(n) = 0.213... n² pentagonal edges, disproving the original conjecture of Erdős. This coefficient is asymptotically the best possible.

Given graphs H and F let E(H,F) denote the set of edges of H which appear in a subgraph isomorphic to F, and let h(n,e,F) denote the minimum of |E(H,F)| among all graphs H of n vertices and e edges. We asymptotically determine h(n,λn^2, C₃) and h(n,λn², C₅) for fixed λ, 1/4 < λ < 1/2. For 2k+1 ≥ 7 we establish the conjecture of Erdős et al. that h(n,cn², C_2k+1) is obtained from the above two-component example.

One of our main tools (beside Szemerédi's regularity) is a new version of Zykov's symmetrization what we can apply for several graphs, simultaneously.

A joint work with Z. Maleki (Isfahan University).