COMBINATORIAL ALGORITHMS GROUP Schedule of Talks: Spring 2010

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 a² + b² = c².

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.

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:

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.

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é)

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 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.

We consider the d-dimensional 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 d-dimensional 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.