KAIST Discrete Math Seminar

In this talk, I attempt to provide a comprehensive introduction to the matroid properties that hold for almost all matroids.
Welsh conjectured that almost all matroids are paving, open for nearly 50 years. If true, the properties of paving matroids translate to almost all matroids, such as non-representability, concentrated ranks, high connectivity and so on. We shall see the related properties that are shown to hold for almost all matroids with some of the proofs. An overview of recent progress and possible further directions will also be presented.

In Bondy and Murty’s book the authors wrote that Tutte conjectured the wheels have the fewest spanning trees out of all 3-connected graphs on fixed number of vertices. The statement can easily be shown to be false and the corrected version, where we fix the number of edges and consider only the planar graphs, were also found to be false. We prove that if we consider the cycles instead of spanning trees then the wheels are indeed extremal. We also establish a lower bound for the number of spanning trees and suggest the prisms as possible extremal graphs.