CAG Schedule of Talks: Spring 2010

Schedule of Talks: Spring 2010

If you would like to give a talk in our seminar series, please contact Wendy Myrvold ( To get e-mail notification of our seminars and other events, you can subscribe to the CAG e-mail list at

Schedule for Talks:

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 Self-stabilizing 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 n-space by cubes
Fri. Apr. 30 2:30pm ECS 660 Cedric Chauve On matrices that do not have the Consecutive-Ones Property

Upcoming Talks:

Tiling n-space by cubes
Peter Horak, University of Washington, Tacoma
Friday April 23, 3:30pm, DSB C118

A lattice tiling T of n-space 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 n-space by unit cubes there must be a pair of cubes that share a complete (n-1)-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 a2 + b2 = c2.

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 n-space by clusters of cubes, namely by spheres in Lee metric, and show how these tilings are related to the perfect error-correcting codes. The Golomb-Welch conjecture, the long-standing and the most famous conjecture in the area, will be discussed. At the end of our talk we will consider tilings by n-crosses, the Lee spheres of radius 1 (if we reflect an n-dimensional cube in all its faces, then the 2n+1 obtained cubes form an n-cross). Some "unexpected" tilings by n-crosses will be presented.

On matrices that do not have the Consecutive-Ones Property
Cedric Chauve, Department of Mathematics, Simon Fraser University
Friday April 30, 2:30pm, ECS 660

There has been a recent renewed interest in the computational biology community for the classical Consecutive-Ones 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 error-free.

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.

Previous Talks:

Tatami Tilings
Alejandro Erickson
Friday Jan. 22, 3pm, ECS 108

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 half-mats is the monomer-dimer 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^{N-1}. We conclude by posing a few open problems including some hardness questions.

This is joint work with Frank Ruskey, Mark Schurch, and Jenni Woodcock.

Self-stabilizing algorithms for the median problem in partial rectangular grids and their relatives
Emmanuel Godard
Laboratoire d'Informatique Fondamentale
University of Aix-Marseille, France
Friday Feb. 26, 2:45pm, ECS 108

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 self-stabilizing algorithm is a distributed algorithm that can recover from any transient fault. We present a self-stabilizing 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è (Aix-Marseille Université)

Local and global properties of graphs.
Omer Angel, Mathematics Department, UBC
Thurs. March 18, 2:30pm, DSB C118

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 and Nonnegative Eigenvalues
Richard A. Brualdi, University of Wisconsin-Madison
Thurs. March 25, 3:30pm, Clearihue A215

(0,1)-matrices are, in particular, nonnegative matrices, and so the Perron-Frobenius 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.

Perfect Matchings in Grid Graphs after Vertex Deletions
Richard Anstee, Department of Mathematics, UBC
Monday March 29, 2:30pm, Maclaurin D103

We consider the d-dimensional grid graph G=Gm^d on vertices {1,2, ... ,m}d (a subset of Zd) 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 md 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 d-dimensional grid graph G which satisfy three conditions
(i) |B'|=|W'|,
(ii) for any x, y in B' then dG(x,y)> a(d) m1/d + b(d), and
(iii) for any x,y in W' then dG(x,y) > a(d) m1/d + b(d),
then G with the vertices B' and W' deleted has a perfect matching. The factor m1/d is best possible.

This is joint work with Jonathan Blackman and Gavin Yang, UBC.

Speeding up random walks with neighborhood exploration
Petra Berenbrink, School of Computing Science, SFU
Friday April 9, 2:30pm, ECS 660

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.

CAG Schedule of Talks: Spring 2010 / maintained by Wendy Myrvold / / revised Apr. 16, 2010