MATH Seminar
| Title: On Erdos' conjecture on the number of edges in 5-cycles |
|---|
| Seminar: Combinatorics |
| Speaker: Zoltan Furedi of Renyi Institute of Mathematics, Budapest, Hungary |
| Contact: Dwight Duffus, dwight@mathcs.emory.edu |
| Date: 2013-12-06 at 4:00PM |
| Venue: W306 |
| Download Flyer |
| Abstract: Erdos, Faudree, and Rousseau (1992) showed that a graph on n vertices and at least $[n^2/4]+1$ edges has at least $2[n/2]+1$ edges on triangles and this result is sharp. They also considered a conjecture of Erdos that such a graph can have at most $n^2/36$ non-pentagonal edges with an extremal graph having two components, a complete graph on $[2n/3]+1$ vertices and a complete bipartite graph on the rest. This was mentioned in other papers of Erdos and also it is No. 27 in Fan Chung's problem book.\\ \\ In this talk we give a graph of $[n^2/4]+1$ edges with much more, namely $n^2/8(2+\sqrt{2})$ + $O(n) = n^2/27.31…$ pentagonal edges, disproving the original conjecture. We show that this coefficient is asymptotically the best possible.\\ \\ Given graphs H and F let $E_0(H,F)$ denote the set of edges of H which do not appear in a subgraph isomorphic to F, and let $h(n,e,F)$ denote the maximum of $|E_0(H,F)|$ among all graphs H of n vertices and e edges. We asymptotically determine $h(n,cn^2, C_3)$ and $h(n,cn^2, C_5)$ for fixed c, $1/4 < c < 1/2$. For $2k+1\ge$ 7 we establish the conjecture of Erdos et al. that $h(n,cn^2, C_{2k+1})$ is obtained from the above two-component example.\\ \\ One of our main tools (beside Szemeredi's regularity) is a new version of Zykov's symmetrization what we can apply for more graphs, simultaneously. |
See All Seminars