CMS/SMC
CanaDAM 2013
Memorial University of Newfoundland, June 10 - 13, 2013 www.cms.math.ca//2013
       

Matroids, Codes and Numbers
Chair: Daryl Funk (Simon Fraser University)
[PDF]

MAX ALEKSEYEV, University of South Carolina
Integral points on biquadratic curves and near-multiples of squares in Lucas sequences  [PDF] [SLIDES]

We describe algorithmic reduction of a search for integral points on a biquadratic curve $y^2 = ax^4 + bx^2 + c$ with integer coefficients $a\ne 0,b,c$ with irreducible right hand side to a finite number of Thue equations. This enables finding all integral points on many curves, using readily available Thue equations solvers.

A particular application of our reduction is finding near-multiples of squares in Lucas sequences. In particular, we establish that among Fibonacci numbers only 1, 2, and 5 are of the form $m^2 + 1$; only 1 and 13 are of the form $3m^2 + 1$; etc.

DARYL FUNK, Simon Fraser University
Unique graph representations of bias matroids  [PDF] [SLIDES]

A classical theorem of Whitney characterises those graphs that represent a given graphic matroid. Bias (also called frame) matroids generalise graphic matroids. Bias matroids include the class of Dowling geometries, and are important in matroid structure theory. A result of Daniel Slilaty gives a sufficient condition for the uniqueness of a biased graph representing a given bias matroid. We present a strengthening of this result, giving a structural characterisation of the biased graphs that represent a given bias matroid. This is joint work with Matt DeVos, Luis Goddyn, and Irene Pivotto.

ATTILA SALI, Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences
A note on binary Armstrong codes  [PDF] [SLIDES]

An Armstrong code $\text{Arm}(q,k,n)$ is a $q$-ary code of length $n$ with minimum distance $d=n-k+1$ and such that for every subset of size $k-1=n-d$ of the coordinate positions there are two codewords that agree there (so the minimum distance occurs `in all directions')

In this note we take $q=2$, and give necessary and sufficient conditions for the existence of an $\text{Arm}(2,k,n)$. We show for binary Armstrong codes $\text{Arm}(2,k,n)$ that asymptotically $n/k \le 1.224$, while such a code is shown to exist whenever $n/k \le 1.12$. We also construct an $\text{Arm}(2,n-2,n)$ and $\text{Arm}(2,n-3,n)$ for all admissible~$n$.

FANXUAN ZENG, Universitat Autonoma de Barcelona
On the minimum distance of q-ary nonlinear codes  [PDF] [SLIDES]

Any error correcting code can be represented as the union of cosets of a linear subcode. We use this structure for storing codes, starting from binary codes, and then generalizing it to general $q$-ary codes. Then, by adapting the existing Brouwer-Zimmerman algorithm for linear codes, we designed new algorithms for computing the minimum weight and distance efficiently.

Derived algorithms are used to perform a decoding process for linear codes, without constructing the syndrome table, which is time costing and in some cases too big to deal with. Similarly, we designed algorithms to compute the covering radius of linear codes.

Event Sponsors

Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathmatiques The Fields Institute Pacific Institute for the Mathematical Sciences Canadian Mathematical Society Memorial University of Newfoundland