Zykov's Symmetrization for Multiple Graphs with an Application to Erdos' Conjecture on Pentagonal Edges

Tuesday, December 2, 2014 - 2:00pm - 3:00pm
Lind 305
Zeinab Maleki (Isfahan University of Technology)
Erdos, Faudree, and Rousseau (1992) showed that a graph on $n$ vertices and at least $\lfloor n^2/4\rfloor+1$ edges has at least $\lfloor n/2\rfloor+1$ edges on triangles. This result is sharp, just add an extra edge to the complete bipartite graph. In this talk, we give an asymptotic formula for the minimum number of edges contained on triangles in a graph having $n$ vertices and $e$ edges. The main tool of the proof is a generalization of Zykov's symmetrization that can be applied for several graphs simultaneously. We apply our weighted symmetrization method to tackle Erdos' conjecture concerning the minimum number of edges on 5-cycles. Many problems remain open.
This is a joint work with Zoltan Furedi.