Abstract
dc:description.abstractA rank-n binary matroid is a spanning subset E of F₂ⁿ\{0}, a triangle is a set of three elements from E which sum to zero, and the density of a rank-n binary matroid is |E|/2ⁿ. We begin by giving a new exposition of a result due to Davydov and Tombak, which states that if E is a rank-n triangle-free matroid of density greater than 1/4, then there is a dimension-(n-2) subspace of F₂ⁿ which is disjoint from E. With this as a starting point, we provide a recursive structural decomposition for all maximal triangle-free binary matroids of density greater than 1/4. A key component of this decomposition is an analogous characterization of matroids which are maximal with respect to containing exactly one triangle. A pentagon in a binary matroid E is a set of 5 elements which sum to zero. We conjecture that if E is a rank-n triangle-free binary matroid, then E contains at most 2^{4n-16} pentagons, and provide a potential extremal example. We first resolve this conjecture when E has density at most ∜(120) /16 ≈ 0.20568. Thereafter, we use our structural decomposition to show that the conjecture holds for matroids with density greater than 1/4. This leaves the interval (∜(120)/16, 1/4], where the conjecture remains unresolved.
Degree
thesis:*- Grantor dc:publisher
- University of Waterloo
- Year dc:date.issued
- 2020
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Brown, Adam
- Advisor dc:contributor.advisor
-
- Nelson, Peter
Subjects
dc:subject × 5Rights
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/10012/16089