From coordinate subspaces over finite fields to ideal multipartite uniform clutters

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.