Matroid Products via Submodular Coupling

Bérczi, Kristóf and Gehér, Boglárka and Imolay, András and Lovász, László and Maga, Balázs and Schwarcz, Tamás Bence (2025) Matroid Products via Submodular Coupling. In: STOC '25: Proceedings of the 57th Annual ACM Symposium on Theory of Computing. Proceedings of the Annual ACM Symposium on Theory of Computing . Association for Computing Machinery (ACM), New York, pp. 2074-2085. ISBN 9798400715105

Preview

Text 2411.02197v2.pdf - Draft Version Available under License Creative Commons Attribution. Download (606kB) | Preview

Abstract

The study of matroid products traces back to the 1970s, when Lov´asz and Mason studied the existence of various types of matroid products with different strengths. Among these, the tensor product is arguably the most important, which can be considered as an extension of the tensor product from linear algebra. However, Las Vergnas showed that the tensor product of two matroids does not always exist. Over the following four decades, matroid products remained surprisingly underexplored, regaining attention only in recent years due to applications in tropical geometry and the limit theory of matroids. In this paper, inspired by the concept of coupling in probability theory, we introduce the notion of coupling for matroids – or, more generally, for submodular set functions. This operation can be viewed as a relaxation of the tensor product. Unlike the tensor product, however, we prove that a coupling always exists for any two submodular functions and can be chosen to be increasing if the original functions are increasing. As a corollary, we show that two matroids always admit a matroid coupling, leading to a novel operation on matroids. Our construction is algorithmic, providing an oracle for the coupling matroid through a polynomial number of oracle calls to the original matroids. We apply this construction to derive new necessary conditions for matroid representability and establish connection between tensor products and Ingleton’s inequality. Additionally, we verify the existence of set functions that are universal with respect to a given property, meaning any set function over a finite domain with that property can be obtained as a quotient.

Actions (login required)

Edit Item