Dense binary PG(t − 1,2)-free matroids have critical number t − 1 or t

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

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 languageEnglish (US)
Pages (from-to)165-179
Number of pages15
JournalJournal of Combinatorial Theory. Series B
Volume124
DOIs
StatePublished - May 1 2017
Externally publishedYes

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