Article ID Journal Published Year Pages File Type
5777625 Journal of Combinatorial Theory, Series B 2017 15 Pages PDF
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.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,