Graphs and Matroids Seminar - Adam Brown

Title: Counting Pentagons in Triangle-free Binary Matroids

Abstract:

Every triangle-free graph with n vertices contains at most (n/5)^5 cycles of length five, and this value is attained by the balanced blowup of the 5-cycle. Each piece of this statement can be translated into the language of binary matroids to formulate an analogous conjecture. We will confirm this new conjecture for sets with density greater than 1/4. Along the way, we give a recursive construction for all large triangle-free sets, and a construction for binary matroids which contain exactly one triangle and the maximum number of elements.