CAG Schedule of Talks: Spring 2011

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

Schedule for Talks:

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

Upcoming Talks

γ-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 D1 and D2, are adjacent in E(γ) if there exists a vertex v in D1 and a vertex w in D2 such that v is adjacent to w and D1= D2 - {w} ∪ {v}, or equivalently, D2 = D1 - {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.

Previous Talks

Transversals in Latin Squares
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.

Settling on a Palette for Rio: Reflexive Injective Oriented Colouring
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:

Pairs of Mutually Orthogonal Latin Squares of Order 10 with Small Dimension
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).

A De Bruijn Cycle for Fixed-Density Binary Strings

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

The classic De Bruijn cycle is a cyclic string of length 2n 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 k-1 exactly once. On average, the algorithm generates each bit of the string in constant time and is based on a new algorithm for generating necklaces (binary strings under rotation) in cool-lex order, a Gray code variant of colex order.

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