You are not logged in | Log in

Minimum number of edges that occur in odd cycles

Speaker(s)
Andrzej Grzesik
Date
Nov. 24, 2016, 12:15 p.m.
Room
room 5870
Seminar
Seminar Algorithms

For any fixed k>1 every graph without a cycle on 2k+1 vertices has at most n^2/4 edges. In 1992, Erdos, Faudree and Rousseau conjectured that if a graph has at least n^2/4 + 1 edges, then already at least 2n^2/9 edges occur in cycles on 2k+1 vertices. In the talk I will disprove this conjecture for k=2 and prove the exact bound for every k>1.