Ottawa-Carleton Discrete Math Days 2011 : Abstracts

Back to DMD 2011 main page.

Invited Talks

Ed Bender University of California at San Diego slides

Locally restricted compositions: past, present and future

Roughly speaking, a locally restricted composition is a composition of an integer in which parts within a given distance of each other are required to satisfy some conditions. Carlitz compositions, in which adjacent parts must be distinct, are a classic example of such compositions. A recurrence requirement rules out partitions. We survey some recent results about the asymptotic behavior of locally restricted compositions including number, joint normality of many parameters, largest part, and probability of gaps. We use combinatorial arguments, generating functions and infinite transfer matrices.

Jim Geelen University of Waterloo

A characterization of graphic matroids by a system of linear equations

Given a rank-$r$ binary matroid we construct a system of $O(r^3)$ linear equations in $O(r^2)$ variables that has a solution over GF$(2)$ if and only if the matroid is graphic. The talk will be self-contained and does not require any prior exposure to matroid theory.

This is joint work with Bert Gerards.

Bill Martin Worcester Polytechnic Institute

Abusing codes

The emergence of turbo codes and low-density parity check codes has left some with the impression that algebraic coding theory is dead. This talk will be a brief survey of several newer uses of error-correcting codes and some of the problems that arise in these new contexts. Selected topics will include numerical integration, random bit generation, biometrics and computational complexity theory.

Wendy Myrvold University of Victoria

Searching for a maximum set of mutually orthogonal latin squares of order $10$

A Latin square of order $n$ is a $n \times n$ array of $n$ symbols such that each symbol appears exactly once in each row and exactly once in each column. Two Latin squares of order $n$ are orthogonal if when superimposed, each ordered pair of symbols occurs exactly once. One of the big unsolved problems in design theory is to determine if it is possible to find three or more pairwise orthogonal Latin squares of order $10$. This talk describes both theoretical and computational attempts at resolving this question. The talk will conclude with some suggestions for promising areas for continued search.

The research presented in this talk was done in collaboration with Erin Delisle, Mark Ellingham, Leah Howard, Nikolay Korovaiko, Brendan McKay, Alison Meynert, and Ian Wanless.

Leonard Soicher Queen Mary, University of London slides

Semi-Latin squares, permutation groups, and statistical optimality

This talk is about a new interaction between certain areas of combinatorial design theory, permutation group theory, and the statistical theory of optimal designs, and is intended to be accessible to a wide discrete-mathematical audience.

Let $n$ and $k$ be integers, with $n>1$ and $k>0$. An $(n\times n)/k$ semi-Latin square $S$ is an $n\times n$ array, whose entries are $k$-subsets of an $nk$-set, the set of symbols of $S$, such that each symbol of $S$ is in exactly one entry in each row and exactly one entry in each column of $S$. For example, here is a $(3\times 3)/2$ semi-Latin square:

1 42 53 6
3 51 62 4
2 63 41 5

Semi-Latin squares generalise Latin squares, and are used in the design of comparative experiments. We give a simple construction to make an $(n\times n)/k$ semi-Latin square $S$ from a transitive permutation group $G$ of degree $n$ and order $nk$, and describe the relationship between certain permutation group properties of $G$ and combinatorial and statistical properties of $S$. In particular, if $G$ is doubly transitive, then $S$ is optimal with respect to a very wide range of statistical optimality criteria.

Contributed Talks

Robert Bailey University of Regina

Resolving sets for incidence graphs

A resolving set for a graph $G$ is a subset of vertices with the property that the list of distances from a vertex to the chosen set uniquely identifies that vertex. The metric dimension of $G$ is the smallest size of a resolving set.

Various authors have studied resolving sets for distance-regular graphs. In this talk, we consider bipartite distance-regular graphs of diameter 3, which are precisely the incidence graphs of symmetric designs. In particular, in the case of projective planes, we show how a well-known object known as a 2-fold blocking set can be used to obtain resolving sets in the incidence graph.

Andrea Burgess Ryerson University

Generalized packing designs

In a 2009 paper, Peter Cameron introduced a common generalization of several combinatorial objects, including $t$-designs, resolvable designs and orthogonal arrays. In this talk, we present a modification of Cameron's definition which yields a common generalization of packing designs and packing arrays. We explore interesting connections between generalized packing designs and various classes of combinatorial designs, and construct optimal generalized packings in certain cases. This is joint work with Robert Bailey.

Andras Farago University of Texas at Dallas

Path optimization in graphs

Finding a path between given vertices in a graph, such that the path is optimal with respect to some metric, is one of the most frequently encountered algorithmic tasks. While finding a shortest path in the classical sense is very easy, with more sophisticated, non-additive path metrics the problem becomes much more difficult, often NP-hard. Given the large variety of practically motivated, but very different path metrics, we consider the question of whether it is possible to represent them in a unified combinatorial framework. We present a framework that allows the unified representation of all such path optimization problems. Within this framework we prove a sufficient condition for the approximability of path optimization in hard cases. Specifically, we define a property of the metric that we call metric width, and prove that any path optimization can be approximated in polynomial time within a factor that is bounded by its metric width. The metric width has the attractive feature that it can be directly read out from the way the metric is represented in our framework. We conjecture that a certain converse of this sufficient condition also holds. If that is indeed true, then it would yield an interesting novel characterization of the approximability of hard path optimization.

Nevena Francetić University of Toronto slides

Covering arrays with row limit

A Covering Array with Row Limit ($CARL$) is a generalization of a covering array, a combinatorial model of a test suite. Compared to a covering array, a $CARL$ has an extra parameter, weight $w$, which allows us to test only $w$ components in each test run. Covering arrays with row limit are related to the group divisible covering designs, the covering designs, and the graph coverings, as well. Depending on the relationship between the weight and the number of components tested, $CARL$s behave in two ways. We are going to illustrate these relationships with different upper bounds on the size of a $CARL$ and some construction methods.

Graeme Kemkes Ryerson University slides

Almost all cop-win graphs have a universal vertex

A cop and a robber take turns moving from vertex to vertex on a graph. We say the graph is cop-win if the cop has a strategy to land on the same vertex as the robber eventually. We show that the proportion of cop-win graphs having a universal vertex (i.e., a vertex adjacent to all other vertices) tends to 1 as the number of vertices grows large.

Joint work with Anthony Bonato and Paweł Prałat.

Andrew MacFie Carleton University

Counting words by number of occurrences of a pattern

Given words $\sigma$ and $\tau$ over an ordered finite alphabet, where $\tau$ is called the pattern, an occurrence of $\tau$ in $\sigma$ is a subsequence of $\sigma$ that is order-isomorphic to $\tau$ — that is, a subsequence of $\sigma$ equal in length to $\tau$ such that the relative order of two elements in the subsequence is the same as the relative order of the corresponding elements of $\tau$. For example, all length 3 subsequences of $\sigma=1234$ are order-isomorphic to $\tau=123$.

Not much is known about the number of words of length $n$ from an alphabet of size $k$ with $r$ occurrences of a pattern for general $r$. For two pattern families, I will present a recurrence followed by an asymptotic expression for this quantity.

Ben Seamone Carleton University

Graph colourings derived from graph weightings

Karoński, Łuczak, and Thomason conjectured that the edges of any graph having no $K_2$ component can be weighted from the set $\{1,2,3\}$ so that any two adjacent vertices have distinct sums of their respective incident edge weights. Their conjecture was inspired by the notion of a graph's irregularity strength, a well known graph parameter introduced by Chartrand, Jacobson, Lehel, Oellermann, Ruiz, and Saba. I will survey some variations on both the ``1,2,3-Conjecture'' and irregularity strength. In particular I will present a variation of the ``1,2,3-Conjecture'' which we have solved, as well as some new open problems which arise from our work.

Joint work with Dr. Brett Stevens

Craig Sloss University of Waterloo slides

A join-cut approach to the $(p,q,n)$-dipole problem

The $(p,q,n)$-dipole problem is a map enumeration problem arising in mathematical physics, specifically, in the study of duality between Yang-Mills theory and string theory. It is a refinement of the problem of enumerating embeddings of a loopless dipole in an orientable surface, which has been solved by working in the centre of the complex algebra generated by the symmetric group. The solution to the $(p,q,n)$-dipole problem does not lie in the centre of the group algebra, and thus, the character-based methods used to study map enumeration problems may not be used. This talk describes how a Join-Cut analysis may be used to study the $(p,q,n)$-dipole problem. A combinatorial argument describing how the addition of an edge to a dipole changes its face structure — i.e. by either cutting a face in two, or joining two faces to become one larger face — is used to determine a pair of partial differential equations for the generating series for $(p,q,n)$-dipoles. While a full solution to these equations is not yet known, there is a process, recursive in genus, for determining the solution for a given orientable surface. Moreover, the genus g solution may be expressed as a positive integral linear combination of a family of functions which is defined as a sum over compositions of a binary string.