It is known that uniform (resp. paving) matroids correspond to MDS (resp. “almost MDS” codes). This post explains this connection.

An MDS code is an linear error correcting block code which meets the Singleton bound, . A uniform matroid is a matroid for which all circuits are of size , where is the rank of *M*. Recall, a *circuit* in a matroid *M=(E,J)* is a minimal dependent subset of *E* — that is, a dependent set whose proper subsets are all independent (i.e., all in *J*).

Consider a linear code whose check matrix is an matrix . The vector matroid *M=M[H]* is a matroid for which the smallest sized dependency relation among the columns of *H* is determined by the check relations , where is a codeword (in *C* which has minimum dimension *d*). Such a minimum dependency relation of *H* corresponds to a circuit of *M=M[H]*.