April 18, 2014

May 9-10, 2013
Ottawa-Carleton Discrete Mathematics Days

to be held at the University of Ottawa

Speaker and Contributed Talk Abstracts (abstracts.pdf)

Andrea Burgess, Ryerson University
Generalized designs, packings and coverings

In 2009, Peter Cameron introduced a common generalization of various classes of combinatorial designs such as balanced incomplete block designs, resolvable designs and orthogonal arrays. Generalized covering and packing designs can be defined in analogous way. These objects bring into this framework further classes of designs, including covering and packing arrays, Howell designs, monogamous cycle decompositions and Kirkman signal sets. In this talk, I will review known results on generalized designs, packings and coverings, and discuss interesting open questions which arise in the search for further examples of optimal generalized packing designs. This talk will include discussions of joint work with Robert Bailey, Michael Cavers, Peter Danziger and Karen Meagher.

Asia Ivic Weis, York University
Combinatorial Structure of Chiral Polyhedra

Classification of regular polyhedra in euclidean 3-space was initiated by Grünbaum in 1977 and completed by Dress by addition of a single polyhedron in 1985. In 2005 Schulte classified the discrete chiral polyhedra in euclidean 3-space and showed that they belong to six families. The polyhedra in three of the families have finite faces and the other three families consist of polyhedra with (infinite) helical faces. We show that all the chiral polyhedra with finite faces are combinatorially chiral. However, the chiral polyhedra with helical faces are combinatorially regular. Moreover, any two such polyhedra with helical faces in the same family are isomorphic.
This is a joint work with Daniel Pellicer.

Karen Meagher, University of Regina
Erdös-Ko-Rado theorem for permutations

Two permutations in the symmetric group on $n$ vertices can be considered to be ``intersecting'' if they both map some $i \in \{1,...,n\}$ to the same element (we say the permutations agree on $i$). With this definition, what is the largest set of permutations such that any two are intersecting? In the last 10 years, several different
proofs have been published that show that the largest such set is either the stabilizer of a point or a coset of the stabilizer of a point. This result is known as the EKR theorem for permutations.
There are several questions that are natural to ask once this result is established. For example what is the largest set of permutations that agree on a set of $t$ elements? There are other ways to define intersection for permutations, does an EKR type result hold for these as well? What is the largest set of intersecting permutations in a subgroup of the symmetric group? I will present some new results by various researchers on these questions.

Bruce Reed, McGill University
How long does it take to catch a drunk miscreant?

We discuss the answer to a question of Churchley who asked how long it will take a cop to catch a drunk robber who moves randomly. We begin by discussing other variants of the cop-robber paradigm. This is joint work with Alex Scott, Colin McDiarmid, and Ross Kang. We rely heavily on work of Komarov and Winkler.

Wenan Zang, University of Hong Kong
When is the Matching Polytope Box-totally Dual Integral?

Let $G=(V,E)$ be a graph. The matching polytope of $G$, denoted by $P(G)$, is the convex hull of the incidence vectors of all matchings in $G$. As shown by Edmonds, $P(G)$ is determined by the following linear system $\pi(G)$:

• $x_e\ge 0$ for each $e\in E$;
• $x(\delta(v))\le 1$ for each $v \in V$;
• $x(E[U])\le \lfloor \frac{1}{2}|U| \rfloor$ for each $U \subseteq V$ with $|U|$ odd.

Cunningham and Marsh strengthened this theorem by showing that $\pi(G)$ is always totally dual
integral. In 1984, Edmonds and Giles initiated the study of all graphs $G$ for which $\pi(G)$ is
box-totally dual integral. The purpose of this talk is to present a structural characterization of
all such graphs. (Joint work with Guoli Ding and Lei Tan.)

Bei Zeng, Guelph University
Symmetries of Codeword Stabilized Quantum Codes

Symmetry is at the heart of coding theory. Codes with symmetry, especially cyclic codes, play an essential role in both theory and practical applications of classical error-correcting codes. Here we examine symmetry properties for codeword stabilized (CWS) quantum codes, which is the most general framework for constructing quantum error-correcting codes known to date. A CWS code Q can be represented by a self-dual additive code S and a classical code C, i.e., Q=(S,C), however this representation is in general not unique. We show that for any CWS code Q with certain permutation symmetry, one can always find a S with the same permutation symmetry as Q such that Q=(S,C). As many good CWS codes have been found by starting from a chosen S, this ensures that when trying to find CWS codes with certain permutation symmetry, the choice of S with the same symmetry will suffice. A key step for this result is a new canonical representation for CWS codes, which is in terms of a unique decomposition as union stabilizer codes. For CWS codes, so far mainly the standard form (G,C) has been considered, where G is a graph state. We analyze the symmetry of the corresponding graph of G, which in general cannot possess the same permutation symmetry as Q. We show that it is indeed the case for toric code on a square lattice with translational symmetry, even if its encoding graph can be chosen to be translational invariant.