The extremal functions of classes of matroids of bounded branch-width

2015/03/27 by Rohan Kapadia, Kapadia, Rohan
Mathematics · #05B35 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05B35

paper · pdf · doi:10.48550/arxiv.1503.07954

25 pages, no figures

arxiv created 2016/01/24 · arxiv updated 2016/01/26

Abstract

For a set of matroids M, let ex_M(n) be the maximum size of a simple rank-n matroid in M. We prove that, for any finite field \mathbbF, if M is a minor-closed class of \mathbbF-representable matroids of bounded branch-width, then lim_{n → ∞} ex_M(n) / n exists and is a rational number, Δ. We also show that ex_M(n) - Δn is periodic when n is sufficiently large and that ex_M is achieved by a subclass of M of bounded path-width.

Related

• Obstructions for matroids of path-width at most k and graphs of linear rank-width at most k
• The densest matroids in minor-closed classes with exponential growth rate
• Stability, fragility, and Rota's Conjecture
• The extremal function for geometry minors of matroids over prime fields
• Matroids denser than a clique