The critical number of dense triangle-free binary matroids

Abstract

We show that, for each real number $\epsilon >0$ there is an integer $c$ such that, if $M$ is a simple triangle-free binary matroid with $|M|\ge (\frac{1}{4}+\epsilon )2^{r(M)}$, then $M$ has critical number at most $c$. We also give a construction showing that no such result holds for any real number less than $\frac{1}{4}$. This shows that the "critical threshold" for the triangle is $\frac{1}{4}$. We extend the notion of critical threshold to every simple binary matroid $N$ and conjecture that, if $N$ has critical number $c\ge 3$, then $N$ has critical threshold $1-i\cdot 2^{-c}$ for some $i\in \{2,3,4\}$. We give some support for the conjecture by establishing lower bounds.

References in corpus (3)

• Coloring dense graphs via VC-dimension
• Finite field models in additive combinatorics
• Odd circuits in dense binary matroids

Cited by in corpus (3)

• An Arithmetic Analogue of Fox's Triangle Removal Argument
• Dense PG(n-1,2)-free binary matroids
• On the structure of dense triangle-free binary matroids