The critical number of dense triangle-free binary matroids

We show that, for each real number $ε> 0$ there is an integer $c$ such that, if $M$ is a simple triangle-free binary matroid with $|M| \ge (\tfrac{1}{4} + ε) 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 $\tfrac{1}{4}$. This shows that the "critical threshold" for the triangle is $\tfrac 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.

No reviews yet.

No comments yet.