Optimizing Extension Techniques for Discovering Non-Algebraic Matroids

2024/06/26 by Bamiloshin, Michael, Farràs, Oriol
#05B35 #94A15 #94A62 #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT)

paper · doi:10.48550/arxiv.2406.18359

Abstract

In this work, we revisit some combinatorial and information-theoretic extension techniques for detecting non-algebraic matroids. These are the Dress-Lovász and Ahlswede-Körner extension properties. We provide optimizations of these techniques to reduce their computational complexity, finding new non-algebraic matroids on 9 and 10 points. In addition, we use the Ahlswede-Körner extension property to find better lower bounds on the information ratio of secret sharing schemes for ports of non-algebraic matroids.

Related

• A Note on Extension Properties and Representations of Matroids
• Information Rates of Minimal Non-Matroid-Related Access Structures
• Algebraic Matroids in Action
• A Formal Analysis of Algorithms for Matroids and Greedoids
• Greedy algorithms and poset matroids