Nicholas Beaton
University of Saskatchewan
Compressed random and self-avoiding walks
Random walks and self-avoiding walks are well-known statistical mechanical models of long, linear polymers in solution.
I'll discuss a model of a polymer sandwiched between two plates being compressed together, and in particular the coefficients
of an associated generating function. The asymptotic behaviour of these coefficients -- for both random walks and self-avoiding
walks-- is unusual, and unlike anything seen in similar polymer models in statistical mechanics.
This is joint work with Tony Guttmann (Melbourne), Iwan Jensen (Melbourne) and Greg Lawler (Chicago).
A preprint is available at http://arxiv.org/abs/1506.00296.
Richard Brewster
Thompson Rivers University
Complexity of circular recolourings
Given two colourings \(f\) and \(g\) of a graph, we say \(f\) recolours to \(g\) if there is a sequence of (proper) colouring starting at \(f\) and ending at \(g\) such that successive colourings differ on a single vertex. For a fixed \(k\), one might ask if all \(k\)-colourings can be obtained by recolouring from some initial colouring \(f\), or for two specific colourings \(f\) and \(g\), is there a recolouring sequence from \(f\) to \(g\)? The computational complexity of the second question is somewhat surprising. Despite the intractability of determining the existence of a \(3\)-colouring, it is polynomial time solvable to determine the existence of a recolouring sequence for two given \(3\)-colourings. This problem becomes PSPACE-complete for \(k \geq 4\).
We examine these questions in the case of circular colourings and prove a similar dichotomy theorem for \((p,q)\)-recolouring: the problem is polynomial for \(p/q < 4\) and PSPACE-complete for \(p/q \geq 4\). We also consider other types of recolouring (not just a single vertex). This is joint work with Sean McGuinness, Ben Moore, and Jon Noel.
Michael Doob
University of Manitoba
Computer software and combinatorics: Transitions and convergence
Combinatorics and computers are old friends. Indeed, the very
first university computers were used to attack the combinatorial problems of the time. The script has changed over time, but the symbiosis between
computers and combinatorics carries on. In this talk we look at both
present and emerging software that will be part of the combinatorial
tool kit. In many ways, what was old is new again; in other cases the
environment and opportunities are really different from what has
previously transpired. Lots of examples will be given.
Karen Gunderson
University of Manitoba
Time for graph bootstrap percolation
Bootstrap processes are types of cellular automata on graphs with two possible states, called `healthy' and `infected'.
For a fixed graph \(F\), the \(F\)-bootstrap process is an update rule for the states of edges in a larger complete graph: starting
from an initial collection of infected edges, a healthy edge becomes infected if it is the only healthy edge in a copy of \(F\) and
infected edges remain infected forever. This process is repeated at discrete time steps and an initial set of infected edges is
said to percolate if every edge is eventually infected. The notion of \(F\)-bootstrap percolation was introduced by
Bollobàs in 1968 with the name weak-saturation. I will give some of the history of the \(F\)-bootstrap process in the
case where the initially infected edges are the edges of an Erdös-Rènyi random graph and will discuss some new results
on the number of steps to percolation in the \(K_r\)-bootstrap process when the initially infected edges are chosen randomly.
Muhammad Ali Khan
University of Calgary
Characterizing the degree sequences of hypergraphs
In 1960, Erdös and Gallai gave necessary and sufficient conditions for the degree sequences of simple graphs. For tournaments, Landau's characterization of the score sequences had existed since 1953. However,
similar questions for hypergraphs are mostly wide open. These questions are important not only for combinatorialists, but also for computer scientists who are interested in efficiently generating graphs and hypergraphs with a given degree sequence. In particular,
finding an Erdös-Gallai type characterization for the degree sequences of simple hypergraphs is an important open problem.
Renate Scheidler
University of Calgary
An Introduction to Hyperelliptic Curve Arithmetic
Elliptic and low genus hyperelliptic curves represent a very suitable setting for public key cryptography, due to their small space requirements, efficient arithmetic and excellent security properties. Elliptic curve cryptography, for example, provides information protection in the Blackberry smartphone, Bluray technology, and other real world applications. The points on an elliptic curve, together with the point at infinity (which functions as the identity element), form an abelian group by virtue of the cord & tangent law that declares any three collinear points on the curve to sum to zero.
While elliptic curves support simpler and faster arithmetic than their hyperelliptic counterparts, this is offset by the fact genus 2 hyperelliptic curves achieve the same level of security with a base field that is half the size of that used for elliptic curves. However, the cord & tangent law no longer holds in higher genus. Instead, the appropriate hyperelliptic generalization of the group of points on an elliptic curve is the degree zero divisor class group (a.k.a. the Jacobian) of the hyperelliptic curve. A higher genus analogue of the cord & tangent law makes it possible to reduce hyperelliptic Jacobian arithmetic to simple polynomial arithmetic.
This talk will provide a survey of elliptic and hyperelliptic curve arithmetic. It is targeted at an audience with no or minimal exposure to cryptography and no prior knowledge of algebraic curves.
Chris Soteros
University of Saskatchewan
Polygons, Polymers and Entangled DNA
The standard discrete models for linear and ring polymers in dilute solution are respectively the self-avoiding walk (SAW)
and self-avoiding polygon (SAP) lattice models. For the simplest SAP model, a ring polymer configuration is represented by a random polygon on a lattice such as the simple cubic lattice and each equal-length polygon is considered to be an equally likely configuration. These models have the advantages that the excluded volume property is easily incorporated and that combinatorial and asymptotic analysis is possible. Furthermore, certain quantities, known as "critical exponents", which characterize how polymer properties scale with polymer size or system temperature are expected to be exactly the same for a lattice model polymer and a real polymer, i.e. they are expected to be "universal". However, despite the simplicity of the models, there are many challenging mathematical questions that remain open about them. In this talk, I will review progress made using SAP models to address questions about the entanglement complexity (knotting and linking) of polymer systems. The work has been motivated in part by experimental studies of: (i) DNA confined to viral capsids, where observed knot frequencies characterize how the DNA is packed in the capsid, and (ii) enzyme action on DNA, where observed knot and link frequencies characterize the action of the enzyme. Methods used include Monte Carlo methods for random generation of polygons and transfer-matrix methods for both asymptotic analysis and exact polygon enumeration and generation.
Gabriel Verret
University of Western Australia
Vertex-primitive digraphs having vertices with almost equal neighbourhoods
A permutation group \(G\) on \(\Omega\) is transitive if for every \(x,y\in\Omega\) there exists \(g\in G\) mapping \(x\) to \(y\). The group \(G\) is called primitive if, in addition, it preserves no nontrivial partition of \(\Omega\).
Let \(\Gamma\) be a vertex-primitive digraph, that is, its automorphism group acts primitively on its vertex-set. It is not hard to see that, in this case, \(\Gamma\) cannot have two distinct vertices with equal neighbourhoods, unless \(\Gamma\) is in some sense trivial.
I will discuss some recent results about the case when \(\Gamma\) has two vertices with ``almost'' equal neighbourhoods, and how these results were used to answer a question of Araùjo and Cameron about synchronising groups. (This is joint work with Pablo Spiga.)
Boting Yang
University of Regina
Zero-Visibility Cops-and-Robber Problems on Graphs
In this talk, we consider the zero-visibility cops-and-robber game, which differs from the classical cops-and-robber game in one way: the robber is invisible. We show that this model is not monotonic. We show that the zero-visibility cop-number of a graph is bounded above by its pathwidth and cannot be bounded below by any nontrivial function of the pathwidth. As well, we define a monotonic version of this game and show that the monotonic zero-visibility cop-number can be bounded both above and below by positive multiples of the pathwidth.
We also consider the computational complexity aspects of the zero-visibility cops-and-robber game. On the one hand we provide an algorithm that computes the zero-visibility cop-number of a tree in linear time. On the other hand, we show that the corresponding decision problem is NP-complete even for starlike graphs. (This is joint work with Dariusz Dereniowski, Danny Dyer and Ryan Tifenbach).
