A rank bound for bases and circuits in binary matroids
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.
Ada: I'm Ada.
Emmy: And I'm Emmy, here with Kolya.
Ada: We're looking at the paper: "A rank bound for bases and circuits in binary matroids".
Emmy: Here's the gist of the paper. Every nonempty simple binary matroid with no coloops satisfies 2b(M) ≥ (r(M) + 1)d(M), with equality if and only if M is isomorphic to the Fano matroid Main Theorem and Bounds The paper establishes a rank bound for bases and circuits in binary matroids, proving that every nonempty simple binary matroid with no coloops satisfies 2b(M) ≥ (r(M) + 1)d(M), with equality holding if and only if M is isomorphic to the Fano matroid F7 This result strengthens a previous rank-independent bound for this class, as the coefficient is sharp for the class as a whole, since b(F7) = 28 and d(F7) = 14.
Ada: Furthermore, it proves that deleting any element leaves at least as many bases as there are circuits in the original matroid, stating that b(M-e) ≥ d(M) for every e ∈ E(M), with equality cases determined by specific structural properties.
Emmy: Basis Growth and Series Extensions The paper investigates basis growth under successive series extensions, providing a sharp linear lower bound: if M is obtained from N by s successive one-element series extensions, then b(M) ≥ b(N) + sd(N).
Ada: The equality conditions for this bound are fully characterized, including cases where E(M) is a circuit or M is a parallel connection of a circuit and a triangle.
Title and authors: Ada: We’re diving into how this paper proves this rank bound for bases and circuits in binary matroids, which is titled "A rank bound for bases and circuits in binary matroids."
Emmy: The authors are Houshan Fu from the School of Mathematics and Information Science at Guangzhou University. They’re using the properties of simple binary matroids to establish a relationship between the number of maximal independent sets, which they call bases, and the number of minimal dependent sets, which are their circuits.
Kolya: So they're connecting these two fundamental counting numbers through rank in a way that seems very rigid for this class of objects.
Ada: Right. They show that even with no coloops—which is a condition meaning no single element is totally independent—this bound holds, and they also prove something about deleting an element.
Emmy: They show that if you take any element out of the matroid, the number of bases remaining stays at least as big as the original number of circuits.
The paper's summary: Ada: To summarize what they did, this paper establishes a rank bound for bases and circuits in binary matroids by proving that two times b of M is greater than or equal to rank of M plus one times d of M.
Emmy: They also establish that the equality holds if and only if the matroid is isomorphic to the Fano matroid. This means F7 is the unique case where this specific relationship becomes an exact equality.
Kolya: That's a very clean characterization of when things are maximally constrained, which is important because it tells us exactly what kind of structure we're dealing with at that point.
Ada: And they go further by showing that deleting any element leaves at least as many bases as there are circuits in the original matroid, stating that b of M minus e is greater than or equal to d of M for every element e in the set.
Emmy: That deletion bound is interesting because it’s not just about one specific structure; it applies to any simple binary matroid with no coloops, and they characterize all the ways that equality can happen for that deletion part.
The paper's improvements: Ada: The paper suggests several ways to improve or refine this understanding of the bound, starting with looking at basis growth under successive series extensions.
Emmy: They investigate what happens when you take a matroid N and add one element at a time, say s times, to get M. They find a sharp linear lower bound on that growth: the number of bases in M is greater than or equal to the number of bases in N plus s times the number of circuits in N.
Kolya: A linear bound like that is powerful because it gives us a predictable way to estimate how fast the basis count grows when we iteratively add elements, and they do characterization for when that equality actually holds.
Ada: They characterize all the conditions where this growth bound becomes an exact equality, which happens if s is zero, or if the resulting matroid M is a circuit itself, or if it’s a parallel connection of a circuit and a triangle.
Conclusion: Emmy: So to wrap up, this paper "A rank bound for bases and circuits in binary matroids" confirms that two times the number of bases is at least rank plus one times the number of circuits, with equality only happening for the Fano matroid.
Ada: And they also gave us a deletion bound: deleting any element still leaves at least as many bases as there are circuits in the original matroid, and they’ve specified when that holds exactly.
Kolya: For me, what sticks is how they handled those series extensions, giving us a clear rule for basis growth under successive additions, which helps control the size of our sample space when building these structures up.
Emmy: It solidifies the relationship between counting bases and circuits through rank in this class of matroids, and it sets up some concrete conditions for when we see that relationship reach its limit.
Ada: And overall, this work provides a very tight tool for analyzing the structure of simple binary matroids by linking these fundamental counts together.
Houshan Fu
Guangzhou University
math.CO
Submitted: 2026-10-08
Updated: 2026-10-31
Comments: 23 pages
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 82/100
The gist: Every nonempty simple binary matroid with no coloops satisfies 2b(M) ≥ (r(M) + 1)d(M), with equality if and only if M is isomorphic to the Fano matroid Main Theorem and Bounds The paper establishes…
Key concepts
- 2b(M)
- This is a rank bound related to the number of bases in a binary matroid M. The paper proves that this quantity is always greater than or equal to (r(M) + 1) times the number of fundamental circuits, with the exception being the Fano matroid.
- Series Extensions
- This refers to building a larger matroid by successively adding one element at a time in series. The paper provides a sharp linear lower bound for how many new bases are created during this process, helping to predict basis growth accurately.
- Weighted Circuit Estimates
- The authors introduce weights assigned to fundamental circuits based on their size relative to the number of bases. These estimates are used to control the error terms that arise when using deletion induction techniques in proving other bounds.
- Joint Circuit Size Exclusions
- This method uses a joint bound derived from Hall's theorem to guarantee that if a matroid structure is missing certain circuit sizes, it must contain a circuit of those excluded sizes. This helps identify forbidden structures.
Terminology
Summary
Every nonempty simple binary matroid with no coloops satisfies 2b(M) ≥ (r(M) + 1)d(M), with equality if and only if M is isomorphic to the Fano matroid
Main Theorem and Bounds
The paper establishes a rank bound for bases and circuits in binary matroids, proving that every nonempty simple binary matroid with no coloops satisfies 2b(M) ≥ (r(M) + 1)d(M), with equality holding if and only if M is isomorphic to the Fano matroid F7 This result strengthens a previous rank-independent bound for this class, as the coefficient is sharp for the class as a whole, since b(F7) = 28 and d(F7) = 14. Furthermore, it proves that deleting any element leaves at least as many bases as there are circuits in the original matroid, stating that b(M-e) ≥ d(M) for every e ∈ E(M), with equality cases determined by specific structural properties. p. 0 For the same class, we prove that deleting any element
leaves at least as many bases as there are circuits in the original matroid: b(M\e) ≥ d(M)
for every e ∈ E(M). We determine all equality cases and deduce a sharp linear lower
bound for basis growth under successive series extensions.Where the paper says it
Basis Growth and Series Extensions
The paper investigates basis growth under successive series extensions, providing a sharp linear lower bound: if M is obtained from N by s successive one-element series extensions, then b(M) ≥ b(N) + sd(N). The equality conditions for this bound are fully characterized, including cases where E(M) is a circuit or M is a parallel connection of a circuit and a triangle. p. 1 Then
b(M\e) ≥ d(M). Equality holds if and only if E(M) is a circuit, or M is a parallel connection of a circuit
and a triangle, with e outside the triangle. Equality holds if and only if E(M) is a circuit, or M is a parallel connection of a circuit
and a triangle, with e outside the triangle. In particular, the inequality is strict when M is
cosimple.Where the paper says it
Where the paper says it
Weighted Circuit Estimates
The authors introduce weighted estimates to control the correction term in the deletion induction, assigning a weight of 1/b(M/C) to each fundamental circuit C such that each j-element circuit contributes total weight j over all bases. They derive joint bounds for circuits of sizes r(M) − 1, r(M), and r(M) + 1, which are used to control the correction term in the deletion induction. p. 3 Oxley also used joint counts for two circuit sizes [3,
proof of Lemma 2. We seek a joint bound for circuits of sizes r(M) − 1, r(M), and
r(M) + 1 that will control the correction term in the deletion induction. 1 Counting and contraction bounds
We first count pairs (B, C) in which B is a basis of M and C is a fundamental circuit with
respect to B. Let X ⊆ E(M), and fix a basis BX of M|X.Where the paper says it
Where the paper says it
Joint Circuit Size Exclusions
The paper develops a method to guarantee distinct bases containing C − e for pairs (C, e) with prescribed circuit sizes J, leading to the inequality Pj∈J jdj (M) ≤ b(M). This is achieved by establishing a local bound on the total weight at a fixed basis using Lemma 5. p. 3 We assign each fundamental circuit C the weight 1/b(M/C), so that each j-element
circuit contributes total weight j over all bases. Rank-one and rank-two contractions control
the local weights, while a folded-cube edge bound controls the joint occurrence of circuits of
sizes r(M) and r(M) + 1. Oxley also used joint counts for two circuit sizes [3,
proof of Lemma 2. We seek a joint bound for circuits of sizes r(M) − 1, r(M), and
r(M) + 1 that will control the correction term in the deletion induction.Where the paper says it
Where the paper says it
Rank-Specific Bounds and Final Results
The paper presents rank-specific bounds derived from analyzing contractions and folded cubes, showing that for rank at least four, Proposition 3.6 provides a bound on the sum of circuit counts in terms of b(M). p. 3 Oxley also used joint counts for two circuit sizes [3,
proof of Lemma 2. We seek a joint bound for circuits of sizes r(M) − 1, r(M), and
r(M) + 1 that will control the correction term in the deletion induction. Section 2 collects the preliminaries. The weighted estimates in Section 3 are used in
Section 4 to prove the main results; Section 5 treats distinct basis extensions. Rank-one and rank-two contractions control
the local weights, while a folded-cube edge bound controls the joint occurrence of circuits of
sizes r(M) and r(M) + 1. Combining these estimates yields Proposition 3. Iterating this identity gives the following
consequence. Corollary 1. Oxley also used joint counts for two circuit sizes [3,
proof of Lemma 2. We seek a joint bound for circuits of sizes r(M) − 1, r(M), and
r(M) + 1 that will control the correction term in the deletion induction. 7)
The following single-element refinement is implicit in the basis-extension argument in [3,
p. 171, proof of Theorem 1. Then
b(M\e) ≥ d(M). Equality holds if and only if E(M) is a circuit, or M is a parallel connection of a circuit
and a triangle, with e outside the triangle.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Verification of Binary Matroid Properties: AI systems can now rigorously check if a given structure is a simple binary matroid with no coloops by applying conditions derived from Theorems 1.1 and 4.1, ensuring that input data conforms to the necessary mathematical constraints for subsequent analyses.
-
Optimized Basis and Circuit Enumeration: The system can now calculate sharp linear lower bounds for basis growth under successive series extensions, using Corollary 1.3, which allows for more accurate prediction of how many bases are created when iteratively adding elements in a specific structure.
-
Circuit-Element Pair Selection: AI systems can employ Theorem 5.2 to determine if a set of required circuit-element pairs has enough distinct bases available to support them, guaranteeing that the number of distinct bases containing C minus e is at least the total count of required extensions.
-
Efficient Circuit Size Exclusion: The system can automatically identify when a joint bound fails for two circuit sizes, immediately concluding that a circuit of the excluded size must exist based on Corollary 5.3, enabling automated detection of forbidden structures in complex matroid representations.
Abstract
Let b(M), d(M), and r(M) denote the number of bases, the number of circuits, and the rank of a matroid M, respectively. Using a weighted count of fundamental circuits, we prove that every nonempty simple binary matroid M with no coloops satisfies [ 2b(M) at least(r(M)+1)d(M),] with equality if and only if M is isomorphic to the Fano matroid. This settles a conjecture recorded by Oxley in 1983. For every e in E(M), we also establish the deletion bound b(M e) at least d(M) and characterize its equality cases. The deletion bound yields a sharp linear lower bound for basis growth under successive series extensions. Finally, under a circuit-size exclusion condition, every pair (C,e) with C a circuit of a prescribed size and e in C can be assigned a distinct basis containing C-e.
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality