On the girth of D(k,q)
Let n and g be positive integers, with 4≤g≤n. What is the greatest number of edges in a graph on n vertices if it contains no cycles of length less than g? This question from extremal graph theory has been studied by many researchers, but the answer is known for only very few infinite families of pairs (n,g). The best general lower bound for the maximum number of edges comes from a family of algebraically defined graphs introduced by Lazebnik, Ustimenko and Woldar, usually denoted by CD(k,q), where k≥2 is an integer, and q is a prime power. It is known that for any q, the length of the shortest cycle (called the girth) in these graphs is at least k+4. It was conjectured that the girth of CD(k,q) is k+4 for k even, and k+5 for k odd. The conjecture is wide open, and it was confirmed only for a few infinite families of pairs of the parameters k and q. In this talk, we will present new infinite families of pairs (k,q) for which the conjecture is true.