CanaDAM 2011
Université de Victoria, 31 mai - 3 juin 2011

Applications of Matroid Theory in Coding Theory I
Org: Irene Márquez Corbella (University of Valladolid)

THOMAS BRITZ, University of New South Wales, Australia
Duality theorems for graphs, codes, and matroids.  [PDF]

Wei's Duality Theorem states a simple, elegant, and fundamental dual property for linear codes. This talk demonstrates how this theorem can be generalised successively to give two very general duality theorems for a broad class of combinatorial objects. Corollary results including new and simple, yet fundamental, duality theorems for graphs and matroids; a new result on matroid designs; and the poset-code generalisation of Wei's Duality Theorem.

GRAHAM FARR, Monash University (Australia)
Transforms, minors, binary functions and generalised Tutte polynomials  [PDF]

We introduce a family of transforms that extends graph- and matroid-theoretic duality. Associated with each such transform are generalised minor operations, which extend deletion and contraction in graphs. We establish how the transforms interact with our generalised minors, extending the classical matroid-theoretic relationship between duality and minors. Composition of the transforms is shown to correspond to complex multiplication of appropriate parameters.

GARY GORDON, Lafayette College
Generalizations of matroid duality  [PDF]

Matroid duality is an important generalization of duality for planar graphs. Using unpublished notes of Brylawski, we extend this notion to arbitrary set systems. This allows one to define a generalized Tutte polynomial. We examine this polynomial for several set systems that are not matroids, and we also investigate the combinatorial significance of duality for these set systems.

RELINDE JURRIUS, Eindhoven University of Technology (Netherlands)
Truncation formulas for invariant polynomials of matroids and geometric lattices.  [PDF]

The truncation of a matroid is obtained by removing all bases from the set of independent sets of the matroid. It was known that the Tutte polynomial of a truncated matroid is determined by the Tutte polynomial of the original matroid. We will give similar formulas for the Möbius and spectrum polynomial. We link to polynomials associated to codes by showing that the truncation of a representable matroid is also representable over an extension field.

Handling of online submissions has been provided by the CMS.


Centre de recherches mathématiques Fields Institute MITACS Pacific Institute for the Mathematical Sciences Société mathématique du Canada University of Victoria