COMBINATORIAL ALGORITHMS GROUP

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

Fri. Jan. 22  3:00pm  ECS 108  Alejandro Erickson  Tatami Tilings 
Fri. Feb. 26  2:45pm  ECS 108  Emmanuel Godard  Selfstabilizing algorithms for the median problem 
Thurs. Mar. 18  2:30pm  DSB C 118  Omer Angel  Local and global properties of graphs. 
Thurs. Mar. 25  3:30pm  Cle A 215  Richard Brualdi  (0,1)Matrices and Nonnegative Eigenvalues 
Mon. Mar. 29  2:30pm  Mac D103  Richard Anstee  Perfect Matchings in Grid Graphs after Vertex Deletions 
Fri. Apr. 9  2:30pm  ECS 660  Petra Berenbrink  Speeding up random walks with neighborhood exploration 
Fri. Apr. 23  3:30pm  DSB C118  Peter Horak  Tiling nspace by cubes 
Fri. Apr. 30  2:30pm  ECS 660  Cedric Chauve  On matrices that do not have the ConsecutiveOnes Property 
A lattice tiling T of nspace by cubes is a tiling where the centers of cubes in T form a group under the vector addition. In 1907 Minkowski conjectured that in a lattice tiling of nspace by unit cubes there must be a pair of cubes that share a complete (n1)dimensional face. Minkowski's problem attracted a lot of attention as it is an interface of several mathematical disciplines. In fact, Minkowski's problem, like many ideas in mathematics, can trace its roots to the Pythagorean theorem a^{2} + b^{2} = c^{2}.
We discuss the conjecture, its history and variations, and then we describe some problems that Minkowski's conjecture, in turn, suggested. We will focus on tilings of nspace by clusters of cubes, namely by spheres in Lee metric, and show how these tilings are related to the perfect errorcorrecting codes. The GolombWelch conjecture, the longstanding and the most famous conjecture in the area, will be discussed. At the end of our talk we will consider tilings by ncrosses, the Lee spheres of radius 1 (if we reflect an ndimensional cube in all its faces, then the 2n+1 obtained cubes form an ncross). Some "unexpected" tilings by ncrosses will be presented.
There has been a recent renewed interest in the computational biology community for the classical ConsecutiveOnes Property (c1P) for binary matrices, motivated by the reconstruction of ancestral genomes. In general, binary matrices obtained from real data do not satisfy the C1P, while they should if the data were errorfree.
In the first part of the talk, I will introduce the notion of Minimal C1P Conflicting Set (MCS) for a given binary matrix M, that are the minimum sets of rows of M that do not satisfy the C1P. I will discuss the combinatorial properties of MCS and several algorithmic questions: counting the number of MCS a row of M belongs to, deciding if a row is part of at least one MCS, generating all MCS. I will present exponential time algorithms for these questions based on old results of Tucker and on the generation of Minimum True Clauses for Monotone Boolean Functions. Work in collaboration with V. You, T. Stephen and U.U. Haus.
In the second part of the talk I will briefly discuss complexity results related to variants of the C1P, where limited gaps are allowed between blocks of 1's. This is joint work with with M. Patterson and J. Manuch.
The Tatami mat is typically a large 2x1 straw mat that was traditionally used to floor the houses of Japanese nobility. It is believed that if a junction between mats forms a "+" shape, they will bring bad fortune. That is, no four mats may meet at a point. The problem of placing mats and halfmats is the monomerdimer tiling problem with the same Tatami condition. First, we show that all such tilings have a rigid structure which admits nice inductive proofs and promises answers to many counting problems on Tatami tilings. Second, we prove that a Tatami tiling of a R x C rectangle has at most Max{R+1,C+1} monomers and that the number of Tatami tilings of a N x N grid with N monomers is N 2^{N1}. We conclude by posing a few open problems including some hardness questions.
This is joint work with Frank Ruskey, Mark Schurch, and Jenni Woodcock.
Given a graph G = (V, E), a vertex v of G is a median vertex if it minimizes the sum of the distances to all other vertices of G. The median problem consists in finding the set of all median vertices of G. A selfstabilizing algorithm is a distributed algorithm that can recover from any transient fault. We present a selfstabilizing algorithm for the median problem in partial rectangular grids. Our algorithm is based on the fact that partial rectangular grids can be isometrically embedded into the Cartesian product of two trees. These trees are closely related to two spanning trees of the partial grid, to which we apply the algorithm proposed by Antonoiu, Srimani (1999) and Bruell, Ghosh, Karaata, Pemmaraju (1999) for computing the medians in trees. Then we extend our approach from partial rectangular grids to some other plane quadrangulations.
This is joint work with Victor Chepoi, Tristan Fevat, and Yann VaxĂ¨ (AixMarseille UniversitĂ©)
I will discuss the relation between the local structure and local properties of a graph (such as vertex degrees and allowed neighborhoods and recurrence of random walk) and global properties such as size and planarity. For example, an elegant result of Benjamini and Schramm states (loosely) that (finitary) planar graphs are uniformly recurrent. The talk relates to works with Szegedy, Sheffield, Silberman, and Wilson.
(0,1)matrices are, in particular, nonnegative matrices, and so the PerronFrobenius theory of nonnegative matrices applies to them. Thus they have a nonnegative eigenvalue that is at least as large as the magnitude of all other eigenvalues. Requiring all eigenvalues to be nonnegative imposes severe restrictions on a matrix. The class of matrices known as totally nonnegative (TNN) matrices is a proper subclass of the class of matrices with only nonnegative eigenvalues. TNN (0,1)matrices have interesting properties and are characterized by four forbidden submatrices.
This talk is based on joint research with Steve Kirkland.
We consider the ddimensional grid graph G=G_{m^d} on vertices {1,2, ... ,m}^{d} (a subset of Z^{d}) where two vertices are joined if and only if their coordinates differ in one place and have a difference of just 1. The graph is bipartite and the m^{d} vertices have bipartition W and B (sets W, B can be determined by the parity of their sum of coordinates).
We show that there are constants a(d), and b(d) so that for every even m,
if we choose subsets B' contained in B and W' contained in W in the
ddimensional grid graph G which satisfy three conditions
(i) B'=W',
(ii) for any x, y in B' then d_{G}(x,y)> a(d) m^{1/d} + b(d), and
(iii) for any x,y in W' then d_{G}(x,y) > a(d) m^{1/d} + b(d),
then G with the vertices B' and W' deleted has a perfect matching.
The factor m^{1/d} is best possible.
This is joint work with Jonathan Blackman and Gavin Yang, UBC.
We consider the following marking process (Rand) made by a random walk on an undirected graph G. Upon arrival at a vertex v, it marks v if unmarked and otherwise it marks a randomly chosen unmarked neighbor of v. We also consider a variant of this process called Rank. Here each vertex is assigned a global random rank first and then in each step, the walk marks the lowest ranked unmarked neighbor of the currently visited vertex.
Depending on the degree and the expansion of the graph, we prove several upper bounds on the time required by these processes to mark all vertices. For instance, if G is a hypercube or random graph, our processes mark all vertices in time O(n), significantly speeding up the THETA(n log n)cover time of standard random walks.
This is joint work with Colin Cooper, Robert Elsaesser, Tomasz Radzik, and Thomas Sauerwald.