This thesis deals with questions relating to the maximum density of rank-n matroids in a minor-closed class.
Consider a minor-closed class M of matroids that does not contain a given rank-2 uniform matroid. The growth rate function is defined by h_M(n) = max(|N| : N ∈ M simple, r(N) ≤ n).
The Growth Rate Theorem, due to Geelen, Kabell, Kung, and Whittle, shows that the growth rate function is either linear, quadratic, or exponential in n. In the case of exponentially dense classes, we conjecture that, for sufficiently large n,
h_M(n) = (q^(n+k) − 1)/(q-1) − c, where q is a prime power, and k and c are non-negative integers depending only on M. We show that this holds for several interesting classes, including the class of all matroids with no U_{2,t}-minor.
We also consider more general minor-closed classes that exclude an arbitrary uniform matroid. Here the growth rate, as defined above, can be infinite. We define a more suitable notion of density, and prove a growth rate theorem for this more general notion, dividing minor-closed classes into those that are at most polynomially dense, and those that are exponentially dense.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:OWTU.10012/6399 |
| Date | January 2011 |
| Creators | Nelson, Peter |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | English |
| Type | Thesis or Dissertation |
Page generated in 0.0024 seconds