标题： 从有限域上的坐标子空间到理想多部分均匀杂乱 显示英文标题

标题： From coordinate subspaces over finite fields to ideal multipartite uniform clutters

摘要： 取一个素数幂$q$，一个整数$n\geq 2$，以及一个坐标子空间$S\subseteq GF(q)^n$在伽罗瓦域$GF(q)$上。 可以将$S$与一个$n$-部$n$-一致的杂乱集合$\mathcal{C}$关联起来，其中每个部分的大小为$q$，并且$S$中的向量与$\mathcal{C}$的成员之间存在双射。 在本文中，我们确定了杂乱结构$\mathcal{C}$何时是理想的，这一性质是在整数规划和组合优化领域的装填与覆盖问题中发展起来的。 有趣的是，表征取决于$q$是否为$2,4$，即某个更高次幂的$2$，或者否则。 每种表征都关键地利用了理想性是一个小图闭合的性质：首先确定排除的小图列表，然后才确定全局结构。 一个关键的见解是，$\mathcal{C}$的理想性仅取决于$S$的基础拟阵。 我们的定理也从理想性扩展到更强的最大流最小割性质。 作为结果，我们证明了这一类杂乱结构的复制和$\tau=2$猜想。 显示英文摘要

摘要： Take a prime power $q$, an integer $n\geq 2$, and a coordinate subspace $S\subseteq GF(q)^n$ over the Galois field $GF(q)$. One can associate with $S$ an $n$-partite $n$-uniform clutter $\mathcal{C}$, where every part has size $q$ and there is a bijection between the vectors in $S$ and the members of $\mathcal{C}$. In this paper, we determine when the clutter $\mathcal{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 $\mathcal{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 $\tau=2$ Conjectures for this class of clutters.