Coordinate-View Confusability Graphs and Matroid Rank Certificates

Abstract

A coordinate-view presentation specifies a large confusability graph by coordinates rather than by an edge list. The problem is to certify zero-error recovery and Shannon capacity from the succinct presentation, before the exponentially large graph is materialized. For affine presentations over ${\mathbb{F}}_q$, Gaussian elimination gives a polynomial-time rank upper certificate from $O(rd\log q+Ld)$ input bits for a graph with $q^r$ vertices. Exactness of that certificate is equivalent to positivity of a Grassmannian avoidance count $N_{t^{\ast }}$. Positivity of $N_k$ is NP-complete for every fixed $k$, already over ${\mathbb{F}}_2$, while the ambient-rank parameter gives a fixed-parameter algorithm. The rank-one reduction is parsimonious for $\#SAT$. For arbitrary $t$, the finite decoder for $N_t$ reads the signed rank profile of the represented forbidden-point matroid; the kernel-intersection lattice alone does not determine the count. On the positive side, kernel sections give the exact formula $\hat{I}˜(G)=\log \hat{I}\pm (G)={\min }_{S\in \mathcal{V}}t(S)\log q$, with a projection-equality matrix optimal for Haemers minrank. A finite-field blocking theorem gives exactness when $q\ge L$, and Reed-Solomon/MDS codes give exact all-$k$-view families beyond that regime. Full-tuple coordinate-view graphs also have a polynomial-time cofinal-antichain normal form; transitive confusability is exactly intersection closure.

Main PDF: 39 pages, 1 figure. Supplementary: 41 pages, 2 tables. Lean 4 artifact available at https://doi.org/10.5281/zenodo.20561409