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
Fingerprint
Dive into the research topics of 'Dense binary PG(t − 1,2)-free matroids have critical number t − 1 or t'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver