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.