Frontiers in Mathematical Sciences

 TITLE On Erdős' Conjecture on Pentagonal Edges and Other Type of Edges SPEAKER Zeinab Maleki Isfahan University of Technology ABSTRACT
 Erdős, Faudree, and Rousseau (1992) showed that a graph on $n$ vertices and at least $\lfloor n^2/4\rfloor + 1$ edges has at least $2\lfloor n/2\rfloor + 1$ edges in triangles. To see that this result is sharp, consider the graph obtained by adding one edge to the larger side of the complete bipartite graph $K_{\lceil n/2 \rceil, \lfloor n/2\rfloor}$. In this talk, we give an asymptotic formula for $h(n, e, K_3)$, the minimum number of edges contained in triangles in a graph having $n$ vertices and $e$ edges, where $e > n^2/4$ arbitrary. The main tool of the proof is a generalization of Zykov's symmetrization method that can be applied for several graphs simultaneously. We apply our weighted symmetrization method to tackle Erdős' conjecture concerning the minimum number of edges on $5$-cycles. We further extend our results to give an asymptotic formula for $h(n, e, F)$, the minimum number of $F$-edges in an $(n, e)$-graph when $n \rightarrow \infty$ and $F$ is a given $3$-chromatic graph. This is a joint work with Zóltan Füredi.