기본 정보
연구 분야
프로젝트
발행물
구성원
preprint|
green
·인용수 0
·2023
From coordinate subspaces over finite fields to ideal multipartite uniform clutters
Ahmad Abdi, Dabeen Lee
arXiv (Cornell University)
초록

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 $τ=2$ Conjectures for this class of clutters.

키워드
MatroidCombinatoricsMathematicsFinite fieldPrime powerIdeal (ethics)Connection (principal bundle)Characterization (materials science)Linear subspaceDiscrete mathematics
타입
preprint
IF / 인용수
- / 0
게재 연도
2023