Abstract
We survey some lower bounds on the function in the title based on matroid theory and address the following problem by Dosa et al. (2004): Determine the smallest number of circuits in a loopless matroid with no parallel elements and with a given size and rank. In the graphic 3-connected case we provide a lower bound which is a product of a linear function of the number of vertices and an exponential function of the average degree. We also prove that, for p≥38, every 3-connected graph with p vertices has at least as many cycles as the wheel with p vertices.