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

Graphs, Hypergraphs, and Computing

22 April 15:30 - 16:30

Zoltan Furedi - University of Illinois at Urbana-Champaign

Erdos, Faudree, and Rousseau (1992) showed that a graph on $n$ vertices with [n^2/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^2 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^2/4]+1 edges with much fewer, namely n^2(2+\sqrt{2})/16 + O(n) = 0.213...n^2 pentagonal edges, disproving the original conjecture of Erdos. This coefficient is asymptotically the best possible.

Given graphs H and F let {\cal 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 |{\cal E}(H,F)| among all graphs H of n vertices and e edges. We asymptotically determine h(n,\lambda n^2, C_3) and h(n,\lambda n^2, C_5) for fixed \lambda, 1/4 < \lambda < 1/2. For 2k+1\ge 7 we establish the conjecture of Erd\H{o}s et al. that h(n,cn^2, C_{2k+1}) is obtained from the above two-component example.

One of our main tools (beside Szemer\'edi'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).
Magnus M. Halldorsson
Reykjavik University
Klas Markström
Umeå University
Andrzej Rucinski
Adam Mickiewicz University
Carsten Thomassen
Technical University of Denmark, DTU


Klas Markström


For practical matters at the Institute, send an e-mail to