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

Matrices and Sequences

Forbidden Configurations: Progress towards a Conjecture  [PDF]

A matrix is simple if it is a (0,1)-matrix with no repeated columns. Given a (0,1)-matrix $F$, we say matrix $A$ has no configuration $F$ if no submatrix of $A$ is a row and column permutation of $F$. Let $|A|$ denote the number of columns in $A$. Define $\hbox{forb}(m,F)=\max\{|A| : A \hbox{ is }m\hbox{-rowed simple matrix with no configuration }F\}$. A conjectured asymptotic bound for $\hbox{forb}(m,F)$ is verified for new $F$. Joint with Sali, Raggi.

DANIEL KATZ, Simon Fraser University
Cross-Correlations of $p$-ary Maximal-Length Sequences: the Few and the Rational  [PDF]

In 1976, Helleseth showed that the cross-correlation function for any pair of $p$-ary maximal-length sequences (that are not cyclic shifts of each other) assumes at least three values. These values were already known to be real algebraic integers, not necessarily rational when the prime $p$ exceeds three. We outline a proof that if the cross-correlation function takes precisely three values, then they must in fact be rational integers.

SHAHLA NASSERASR, University of Regina
Totally Positive Shapes and TP$_k$-completable Patterns  [PDF]

The notions of TP$_k$ and of contiguity are generalized to shapes (a generalization of matrices). The relationship between positivity of contiguous minors and all minors is characterized for shapes. This and other ideas are used to address the TP$_k$-completion problem. In case $ k = 2$, a near characterization of TP$_2$-completable patterns is given.

MURRAY PATTERSON, University of British Columbia
The Gapped Consecutive-Ones Property  [PDF]

A binary matrix $M$ has the $(k,\delta)$-Consecutive-Ones Property (C1P) if the columns of $M$ can be ordered such that each row contains at most $k$ blocks of $1$'s, and no two neighboring blocks are separated by a gap of more than $\delta$ $0$'s. Here we show that for every unbounded or bounded $k\geq 2, \delta \geq 1$, except when $(k,\delta)=(2,1)$, deciding the $(k,\delta)$-C1P is NP-complete, as well as an interesting case that is polynomial-time decidable.

Genetic Algorithms in Forbidden Configurations  [PDF]

A (0,1)-matrix is simple if it has no repeated columns. Given (0,1)-matrix $F$, define $F\nleq A$ if there is no submatrix of $A$ which is row and column permutation of $F$. Given $m\in\mathbb{N}$, define $\hbox{forb}(m,F)=\max\{\#\hbox{ of columns of }A : A \hbox{ is }m\hbox{-rowed, simple, }F\nleq A\}$

We'll discuss the use of Genetic Algorithms to find this combinatorial quantity and give some examples in which this technique proved useful in constructing proofs.

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