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

Applied Combinatorics and the Natural Sciences II
Chair: Marni Mishna (Simon Fraser University)
Org: Marni Mishna (Simon Fraser University), Chris Soteros (University of Saskatchewan) and Karen Yeats (Simon Fraser University)
[PDF]

TOM BOOTHBY, Simon Fraser University
Topological Metrics on Permutations  [PDF]

In comparative genomics, biologists measure the similarity between genomes by modelling genome rearrangements. These metrics often correspond to lengths of factorizations of (signed) permutations into products from certain generating sets, for example block interchanges, or signed reversals. We draw an analogy to topological graph theory in which block interchanges naturally correspond to handles and signed reversals correspond to crosscaps, and investigate associated metrics used in comparative genomics.

SOPHIE BURRILL, Simon Fraser University
Using generating trees to construct Skolem sequences  [PDF]

A Skolem sequence is a linear arrangement of the multiset {1,1,2,2,...,n,n} such that if r appears in positions i and j, then |i-j|=r. We first translate the problem to a particular set of perfect matchings, and then apply the method of generating trees for open arc diagrams to generate exhaustively all Skolem sequences of a given size. Tracking arc length between pairs of vertices in an arc diagram is the central task. Although we do not surpass previously known enumerative results, this method drastically reduces the search space compared to previously known methods.

E. J. JANSE VAN RENSBURG, York University
Some results on inhomogeneous percolation  [PDF] [SLIDES]

Let $\mathbb{L}_0$ contain the origin and be an $s$-dimensional hypercubic sub-lattice of the $d$-dimensional hypercubic lattice $\mathbb{L}$ ($2\leq s <d$). Percolation at densities $(p,\sigma)$ is set up by declaring edges in $\mathbb{L}_0$ open with probability $\sigma$, and edges in $\mathbb{L}\setminus \mathbb{L}_0$ open with probability $p$. We prove existence of a critical curve $\sigma^*(p)$ such that the model is subcritical if $\sigma<\sigma^*(p)$. We show $\sigma^*(p)$ is strictly decreasing with $p\in(0, p_c(d))$, and $\sigma^*(p) = 0$ if $p\in (p_c(d), 1)$ (with $p_c(d)$ the critical density for homogeneous percolation in $\mathbb{L}$). Results about the critical point and cluster distributions will also be given.