From coordinate subspaces over finite fields to ideal multipartite uniform clutters

Abdi, Ahmad and Lee, Dabeen (2024) From coordinate subspaces over finite fields to ideal multipartite uniform clutters. Mathematical Programming. ISSN 0025-5610

Text (s10107-024-02155-3) - Published Version Available under License Creative Commons Attribution. Download (756kB)

• Author
• Scopus publication

Abstract

Take a prime power q, an integer n≥2, and a coordinate subspace S⊆GF(q) n over the Galois field GF(q). One can associate with S an n-partite n-uniform clutter C, where every part has size q and there is a bijection between the vectors in S and the members of C. In this paper, we determine when the clutter C is ideal, a property developed in connection to Packing and Covering problems in the areas of Integer Programming and Combinatorial Optimization. Interestingly, the characterization differs depending on whether q is 2, 4, a higher power of 2, or otherwise. Each characterization uses crucially that idealness is a minor-closed property: first the list of excluded minors is identified, and only then is the global structure determined. A key insight is that idealness of C depends solely on the underlying matroid of S. Our theorems also extend from idealness to the stronger max-flow min-cut property. As a consequence, we prove the Replication and τ=2 Conjectures for this class of clutters.

Item Type:	Article
Official URL:	https://link.springer.com/journal/10107
Additional Information:	© 2024 The Author(s)
Divisions:	Mathematics
Subjects:	Q Science > QA Mathematics
Date Deposited:	06 Nov 2024 14:33
Last Modified:	20 Sep 2025 02:31
URI:	http://eprintstest.lse.ac.uk/id/eprint/125966

Actions (login required)

View Item