Abstract
The critical threshold of a (simple binary) matroid N is the infimum over all ρ such that any N-free matroid M with |M|<ρ2r(M) has bounded critical number. In this paper, we resolve two conjectures of Geelen and Nelson, showing that the critical threshold of the projective geometry PG(t−1,2) is 1−3⋅2−t. We do so by proving the following stronger statement: if M is PG(t−1,2)-free with |M|<(1−3⋅2−t)2r(M), then the critical number of M is t−1 or t. Together with earlier results of Geelen and Nelson [9] and Govaerts and Storme [11], this completes the classification of dense PG(t−1,2)-free matroids.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 165-179 |
| Number of pages | 15 |
| Journal | Journal of Combinatorial Theory. Series B |
| Volume | 124 |
| DOIs | |
| State | Published - May 1 2017 |
| Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
Keywords
- Critical threshold
- Matroids