Georgia Institute of Technology College of Sciences

Let C(G) denote the set of lengths of cycles in a graph G. In this talk I shall present the recent proofs of two conjectures of P. Erdos on cycles in sparse graphs. In particular, we show that if G is a graph of average degree d containing no cycle of length less than g, then as d -> \infty then |C(G)| = \Omega(d^{\lfloor (g - 1)/2 \rfloor}). The proof is then adapted to give partial results on three further conjectures of Erdos on cycles in graphs with large chromatic number. Specifically, Erd\H{o}s conjectured that a triangle-free graph of chromatic number k contains cycles of at least k^{2 - o(1)} different lengths as k \rightarrow \infty. We define the {\em independence ratio} of a graph G by \iota(G) := \sup_{X \subset V(G)} \frac{|X|}{\alpha(X)}, where \alpha(X) is the independence number of the subgraph of G induced by X. We show that if G is a triangle free graph and \iota(G) \geq k, then |C(G)| = \Omega(k^2 \log k). This result is sharp in view of Kim's probabilistic construction of triangle-free graphs with small independence number. A number of salient open problems will be presented in conclusion. This work is in part joint with B. Sudakov. Abstract