 CanaDAM 2013 Memorial University of Newfoundland, June 10 - 13, 2013 www.cms.math.ca//2013 français conference home canadam home

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.

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$.
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.