## COMBINATORIAL ALGORITHMS GROUP Schedule of Talks: Spring 2011 |

If you would like to give a talk in our seminar series, please contact Wendy Myrvold (wendym@cs.uvic.ca). To get e-mail notification of our seminars and other events, you can subscribe to the CAG e-mail list at http://mailman.csc.uvic.ca/mailman/listinfo/cag

Date | Place | Time | Speaker | Abbreviated Title |
---|---|---|---|---|

Fri. Jan. 28 | ECS 660 | 2:30pm | Ian Wanless | Transversals in Latin Squares |

Fri. Feb. 11 | _ | _ | No CAG. | Coast Combinatorics Workshop this weekend |

Mon. Feb. 28 | HSD A270 | 10:00am | Russell Campbell | Reflexive Injective Oriented Colouring |

Fri. Mar. 4 | ECS 660 | 2:30pm | Wendy Myrvold | Pairs of MOLS of Order 10 with Small Dimension |

Fri. Mar. 4 | ECS 660 | 2:30pm | Frank Ruskey | A De Bruijn Cycle for Fixed-Density Binary Strings |

Fri. Mar. 11 | _ | _ | No CAG. | SE Conference |

Thurs. Apr. 28 | HHB 120 | 2:30pm | Stephen Hedetniemi | γ-Graphs of Graphs |

Stephen Hedetniemi

School of Computing, Clemson University

Thurs. Apr. 28, 2:30pm, HHB 120

A set S ⊆ V is a *dominating set* of a graph G=(V,E)
if every vertex in V-S is adjacent to at least one vertex in S. The
*domination number γ(G)* of G equals the minimum cardinality of a
dominating set S in G; we say that such a set S is a *γ-set*.
In this talk we consider the family of all γ-sets in a graph G
and we define the γ-graph G(γ)=(V(γ),E(γ)) of G
to be the graph whose vertices V(γ) correspond 1-to-1 with the
γ-sets of G, and two γ-sets, say D_{1} and D_{2}, are adjacent
in E(γ) if there exists a vertex v in D_{1} and a vertex
w in D_{2} such that v is adjacent to w and D_{1}= D_{2} - {w} ∪ {v},
or equivalently, D_{2} = D_{1} - {v} ∪ {w}. In this talk we initiate
the study of γ-graphs of graphs.
This is joint work with Gerd Fricke, Sandra M.
Hedetniemi and Kevin R. Hutson.

Ian Wanless

School of Mathematical Sciences. Monash University

Fri. Jan. 28, 2:30 pm, ECS 660

A *latin square* of order *n* is an *n* by *n* array of *n* symbols in which each symbol
occurs exactly once in each row and column. A *transversal* of such a square is
a set of *n* entries containing no pair of entries that share the same row, column
or symbol. For example, here is a transversal in a latin square of order 4:

For such a simple idea, transversals have a lot of applications in algebra, geometry and experiment design, for example. Plus they are fun to play with. In this talk I will survey what we know, and what we would like to know, about transversals and their generalisations. The history of the subject goes back to Euler in the 18th Century, but exciting progress has been made recently. No prior knowledge will be assumed.

Russell Campbell

Mon. Feb. 28, 10:00am, HSD A 270

Don't worry about wearing a smock- we won't be painting. No previous knowledge of graph colouring will be assumed. We will start with a quick introduction to colouring graphs, and increase the conditions on colourings until we arrive at reflexive injective oriented colouring, or rio-colouring for short. Then we will show the problem of answering whether an oriented graph is k-rio-colourable becomes NP-complete for values of k >= 3. The complexity proof of this problem exposes a delicate structure result which we have called the Neighbour-juggling Graph. Because the decision problem is polynomial-time solvable for k=2, we present the characterization of graphs that are 2-rio-colourable. From there, we discuss rio-cliques, and their implication on bounds for the rio-chromatic number, which can be improved when restricting ourselves to oriented trees. Finally, we present an efficient algorithm for colouring oriented trees. Be inspired to take a riverboat ride down the Rio-Grande afterwards as a self-reward for learning a new way of colouring graphs.

On Friday March 4, CAG will have two short talks in preparation for the 42nd SE International Conference on Combinatorics, Graph Theory and Computing:

Wendy Myrvold

Fri. Mar. 4, 2:30pm, ECS 660

A *Latin square* of order *n *is a *n x 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 pairwise orthogonal
Latin squares of order 10. A pair of mutually orthogonal Latin
squares (MOLS) of order 10 can be represented as a binary matrix
whose dimension can be computed modulo two. We generated all pairs
of MOLS of order 10 with dimension 35 or less and concluded that
if there is a triple of MOLS of order 10 then each pair of MOLS
in the triple corresponds to an array of dimension 36 or 37. The
search determined that no pairs of dimension 33 or less exist
and that only 6 pairs of MOLS (up to main class equivalence)
have dimension 34 (these are counterexamples to a conjecture
of Moorhouse).

This is joint work with Erin Delisle (Univ. of Toronto) and Leah Howard (Univ. of Victoria).

Frank Ruskey

Fri. Mar. 4, 2:30pm, ECS 660

The classic De Bruijn cycle is a cyclic string of length 2^{n} that
contains every bitstring of length *n *as a substring exactly once.
We show how to efficiently construct a cyclic string of length
*(n choose k)* which contains every substring of length *n-1*
with density *k* or

This is joint work with Joe Sawada (Guelph University) and Aaron Williams (Carleton University).

CAG Schedule of Talks: Spring 2011 / maintained by Wendy Myrvold / wendym@cs.UVic.ca / revised Feb. 21, 2011