Random Deletion for Circuits in Regular Matroids

1.1 Our Results

• The number of circuits of size at most αg is m^O(α), improving Gurjar and Vishnoi’s m^O(α²) bound and resolving the conjecture of Khanna, Putterman, and Song.The bound also yields a randomized enumeration algorithm for near-minimum circuits.Source: §1 · p. 4
• With probability at least 1−1/m^5, random deletion returns an independent set; for a fixed circuit of size at most αg, survival has probability at least m^−O(α) and conditioned nullity is O(α log(α+2)) with high probability.Nullity is the minimum number of elements that must be removed to make the set independent.Source: §1 · p. 3, §1.1 · p. 4
• The results give parallel algorithms for shortest circuits and near-minimum-circuit enumeration, an O(log m)-round independence-oracle basis algorithm, and improved bounds for regular codes and TU lattices.The shortest-circuit algorithm does not require computing Seymour’s decomposition.Source: §1 · p. 4, §1.1 · pp. 5–6

1.2 Overview of Techniques and AI Disclosure

• The approach grew from a graph-cycle deletion argument: an initial O(α²) nullity bound was sharpened to O(α log(α+2)) using structural results on regular matroids.The analysis also identifies a direct recursive approach through Seymour’s sums as insufficient because circuits can span both component matroids.Source: §1.2 · pp. 6–7

Clean unordered decomposition tree.

• A clean decomposition tree ensures each cographic 3-sum boundary matches the three edges incident to a degree-three graph vertex, a property used in the absorption step.The authors infer such a tree using results of Aprile and Fiorini.Source: Clean unordered decomposition tree · p. 7

Matroid absorption.

• Matroid absorption replaces an attached component with weighted elements so circuit projections become circuits in a modified weighted matroid.For a 3-sum, it uses a Δ-Y transformation and relies on the clean decomposition to preserve a basic matroid type.Source: Matroid absorption · p. 7

Random Deletion returns an Independent Set.

• The independence proof assigns good events to decomposition-tree nodes and uses certificates whose survival would witness failure, then bounds the probability that any certificate survives.Absorption reduces each node’s analysis to a modified weighted basic matroid.Source: Random Deletion returns an Independent… · p. 8

2.1 Basic Matroid Terminology

• A matroid’s circuits are inclusion-minimal dependent sets, and nullity is the minimum number of elements to remove to make a set independent.Deletion removes circuits meeting the deleted set; rank and independence oracles provide standard access to matroid information.Source: §2.1 · pp. 9–10

2.2 Graphic and Cographic Matroids

• Graphic matroid circuits are graph cycles, while cographic matroid circuits are minimal edge cuts; known bounds count near-shortest cycles and near-minimum cuts.Subramanian’s bound is (2m)^⌈2α⌉ for cycles of weight at most α times the minimum, and Karger’s is n^2α for cuts.Source: §2.2 · p. 10

2.3 Binary and Regular Matroids

• Regular matroids are representable over every field and therefore binary; binary matroids of nullity at most d contain at most 2^d − 1 circuits.All circuits can be enumerated with O(2^d m) independence queries and 2^d poly(m) time.Source: §2.3 · p. 11

2.4 Matroid Sums and Seymour’s Decomposition Theorem

• Seymour’s theorem constructs every regular matroid from graphic matroids, cographic matroids, and R10 using 1-, 2-, and 3-sums.For binary matroids, sums combine symmetric differences of unions of circuits whose intersections with the shared set agree.Source: §2.4 · pp. 11–12

3.1 Definitions and Structural Properties

• A regular matroid has an unordered decomposition tree with at most 2m nodes and total boundary-set size O(m).Sums along the tree may be performed in any order, and the assembled matroid is isomorphic to the original matroid.Source: §3.1 · pp. 13, 15
• Each circuit has a unique decomposition into empty sets or node circuits, with nonempty projections forming a connected subtree.Across each tree edge, the projections agree on the boundary set and share at most one element; connected-subtree projections are empty or circuits.Source: §3.1 · pp. 15–16

3.2 Clean Refinement

• Every regular matroid admits a clean unordered decomposition tree whose node matroids are graphic, cographic, or isomorphic to R10.At cographic nodes that are not graphic, each three-element boundary set consists of the edges incident to one degree-three vertex.Source: §3.2 · pp. 16–17

4 Matroid Absorption

• Absorption replaces selected attached components with weighted elements, allowing circuit projections to be analyzed in a modified matroid.The replacement weights account for elements used inside the attached components.Source: §4 · p. 19, §4.1 · p. 19

4.1 Completion and Expansion

• Completions replace boundary elements in a circuit, and the absorption lemma gives a weight-preserving bijection between eligible original circuits and circuits in the modified matroid.The correspondence applies to circuits meeting each selected boundary set in at most one element; the weight of the modified circuit equals the expansion size.Source: §4.1 · p. 21

4.2 Graphic Matroids

• For graphic matroids, absorption replaces each selected 3-sum triangle with a weighted three-edge star, while retaining edges associated with 2-sums.The resulting graphic matroid satisfies the absorption lemma.Source: §4.2 · pp. 21–22

4.3 Cographic Matroids

• For cographic matroids that are not graphic, absorption replaces a selected 3-sum star with a weighted triangle and establishes the absorption lemma.The resulting matroid is cographic, with the required circuit correspondence and expansion weights.Source: §4.3 · p. 23

4.4 Proof of Lemma 11

• When the node matroid is isomorphic to R10, selected attachments are only 2-sums, so absorption leaves the matroid unchanged and assigns weights to its elements.The original and modified circuits correspond directly, with weights preserving expansion size.Source: §4.4 · p. 25

5.1 Rooted Decomposition and Good Events

• A node is R-good when its subtree contains no surviving circuit avoiding its boundary and every surviving boundary completion has size less than g/2.At the root, whose boundary is empty, R-goodness is equivalent to R being independent; any completion of size less than g/2 is unique.Source: §5.1 · p. 26

5.2 Absorbing Child Components

• Absorbing child components into a weighted matroid turns any node that is not R-good despite R-good children into a circuit certificate of weight at least g/2.The corresponding circuit expansion lies in R outside the parent boundary and meets that boundary in at most one element.Source: §5.2 · p. 27

5 Random Deletion returns an Independent Set

• If no certificate survives anywhere in the decomposition tree, induction from the leaves shows every node is R-good and the remaining set is independent.The proof outline connects certificate non-survival to R-goodness at the root, which is equivalent to independence.Source: §5.1 · p. 26, §5.2 · p. 28

5.3 Certificates at Graphic Nodes

• At a graphic node with m_u elements, at most 3m_u^2 certificates suffice, each of size at least g/2, to witness failure of R-goodness when all children are R-good.The certificates consist of sufficiently long edge expansions or admissible simple path expansions.Source: §5.3 · pp. 29–30

5.4 Certificates at Cographic Nodes

• At cographic nodes, the analysis constructs certificates and bounds their survival probabilities using circuit expansions corresponding to graph cuts.The symmetric difference of cuts is again a cut, allowing application of Karger’s cut counting bound.Source: §5 · p. 25, §5.4 · p. 31
• At a cographic node, at most 5(2mu)^4alpha circuits meet the parent boundary in at most one element and have weight at most alpha g.This count supports bounding the number of small certificates.Source: §5.4 · pp. 31–32
• At a cographic node, each certificate W lies in EQu \ Su, has size at least g/2, and is contained in R when u is not R-good but all its children are R-good.Among certificates of size at most alpha g, there are at most 5(2mu)^4alpha.Source: §5.4 · pp. 32–33

5.5 Proof of Theorem 1

• At each R10 node, certificates are expanded circuits with at least g/2 elements outside the parent boundary; if the node is not X-good while its children are, one such set lies in X.R10 has at most 1024 circuits, which bounds the number of candidate certificates.Source: §5.5 · pp. 33–34
• If no node certificate is contained in R, induction from the leaves shows every node is R-good, so R is independent.The proof bounds the probability of dependence by a union bound over at most 2m nodes, using mu ≤ m for every node.Source: §5.5 · p. 34

6.1 Minimum Circuit Bound for Regular Matroids

• A regular matroid can be reduced to one with the same nullity, O(s^2) elements, and minimum-circuit-to-ground-set ratio at least half the original.This reduction lets the proof replace log m with O(log(s + 1)) when deriving the minimum-circuit bound.Source: §6.1 · pp. 35–37

6.2 Nullity conditioned on Circuit Survival

• If a circuit C has size at most αg and its contracted-and-restricted matroid has nullity at least ⌈220α ln(α + 2)⌉, that matroid contains a circuit of size at most g/40.Source: §6.2 · p. 37

6.3 Counting and Enumerating Near-Minimum Circuits

• Repeated independent sampling, nullity filtering, and circuit enumeration return all circuits of size at most αg with high probability in m^O(α) time.When g is unknown, trying every integer guess increases the running time by a factor of m.Source: §6.3 · p. 40
• By Theorem 2, each fixed circuit of size at most αg survives with the required nullity bound with probability at least m−O(α) per repetition; mO(α) independent repetitions return all such circuits with high probability.Source: §6.3 · p. 40

• A binary matroid with nullity at most d has at most 2^d − 1 circuits, enumerable with O(2^d m) independence queries and 2^d poly(m) time.Source: A Circuits in Binary Matroids with… · p. 43
• The enumeration encodes each circuit by its intersection with the nonbasis elements, then tests candidate subsets for being circuits.The proof uses that symmetric differences of circuits in a binary matroid decompose into circuits, while a basis is independent.Source: A Circuits in Binary Matroids with… · p. 43