On the Number of Circuits in Regular Matroids (with Connections to Lattices and Codes)

2018/07/13 by Rohit Gurjar, Gurjar, Rohit, Nisheeth K. Vishnoi +1 · 1 citation
Computer Science · Engineering · #Advanced Graph Theory Research #Coding theory and cryptography #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1807.05164

openalex publication_date 2018/07/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We show that for any regular matroid on m elements and any α≥ 1, the number of α-minimum circuits, or circuits whose size is at most an α-multiple of the minimum size of a circuit in the matroid is bounded by m^O(α2). This generalizes a result of Karger for the number of α-minimum cuts in a graph. As a consequence, we obtain similar bounds on the number of α-shortest vectors in "totally unimodular" lattices and on the number of α-minimum weight codewords in "regular" codes.

Cited by

• Optimal Parallel Basis Finding in Graphic and Related Matroids

Related

• Circuit decompositions of binary matroids
• The k-fold circuit property for matroids
• How many circuits determine an oriented matroid?
• The maximum number of minimal codewords in long codes
• On Optimization and Counting of Non-Broken Bases of Matroids