Interaction Between Skew-representability, Tensor Products, Extension Properties, and Rank Inequalities

Bérczi, Kristóf and Gehér, Boglárka and Imolay, András and Lovász, László and Padró, Carles and Schwarcz, Tamás (2026) Interaction Between Skew-representability, Tensor Products, Extension Properties, and Rank Inequalities. In: Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics (SIAM), Philadelphia, pp. 328-354. ISBN 9781611978971

Preview

Text 1.9781611978971.15.pdf - Published Version Download (726kB) | Preview

Abstract

Skew-representable matroids form a fundamental class in matroid theory, bridging combinatorics and linear algebra. They play an important role in areas such as coding theory, optimization, and combinatorial geometry, where linear structure is crucial for both theoretical insights and algorithmic applications. Since deciding skew-representability is computationally intractable, much effort has been focused on identifying necessary or sufficient conditions for a matroid to be skew-representable. In this paper, we introduce a novel approach to studying skew-representability and structural properties of matroids and polymatroid functions via tensor products. We provide a characterization of skew-representable matroids, as well as of those representable over skew fields of a given prime characteristic, in terms of tensor products. As an algorithmic consequence, we show that deciding skew-representability, or representability over a skew field of fixed prime characteristic, is co-recursively enumerable: that is, certificates of non-skewrepresentability - in general or over a fixed prime characteristic can be verified. Finally, as an application of the tensor product framework, we derive the first known linear rank inequality for folded skew-representable matroids that does not follow from the common information property.

Actions (login required)

Edit Item