Matroid Properties of Linear Codes

Speaker: 

Jessica Dai

Affiliation: 

University of New South Wales

Date: 

Tue, 22/05/2018 - 12:00pm to 1:00pm

Venue: 

RC-4082, The Red Centre, UNSW

Abstract: 

Various parameters of a linear code, such as its minimum weight and minimum distance, provide information about its error-detecting and error-correcting capabilities. In 1963, MacWilliams proved her widely celebrated MacWilliams Identity, which relates the weight enumerator of a code to the weight enumerator of its dual.

 

The columns of a linear code’s generator matrix form a combinatorial structure called a matroid. Matroids were introduced by Whitney in 1935 as an abstraction of linear independence in vector spaces and cycles in graphs. In 1976, Greene proved the weight enumerator of a linear code is an evaluation of the Tutte polynomial of the code’s associated matroid. This resulted in a simple proof of the MacWilliams Identity and established a new intrinsic link between coding theory and combinatorics. More recently, Duursma provided a matroid proof of Wei's Duality Theorem, another important result in coding theory.

 

We investigate generalisations of Greene’s results to higher weights, codeword tuples and larger classes of codes. Of particular interest is how these results may be extended to codes over rings, which exhibit more optimal error-correcting properties than linear codes. These generalisations can be viewed as generalisations of a stronger result in matroid theory, the Critical Theorem by Crapo and Rota in 1970.

School Seminar Series: