UW-PIMS Colloquia Archive 2008-2009
 
April 24, 2009
Glenn Tesler
UC San Diego		 Reconstructing the Genomic Architecture of Ancestral Mammals
In addition to frequent single-nucleotide mutations, mammalian and many other genomes undergo rare and dramatic changes called genome rearrangements. These include inversions, fissions, fusions, and translocations. Although analysis of genome rearrangements was pioneered by Dobzhansky and Sturtevant in 1938, we still know very little about the rearrangement events that produced the existing varieties of genomic architectures. Recovery of mammalian rearrangement history is a difficult combinatorial problem that I will cover in this talk. Our data sets have included sequenced genomes (human, mouse, rat, and others), as well as radiation hybrid maps of additional mammals.

Co-authors:
Pavel Pevzner, UCSD, Department of Computer Science and Engineering
Guillaume Bourque, Genome Institute of Singapore
 
April 3, 2009
Robert Bryant
UC Berkeley		 Auf Wiedersehen Surfaces, Revisited

It has been known for over a century that there are many Riemannian metrics on the 2-sphere with the property that all of their geodesics are closed. Zoll, a student of Hilbert, constructed an infinite dimensional family of surfaces of rotation with this property. Following ideas of Funk, Guillemin proved that these metrics on the 2-sphere are essentially parametrized by the odd functions on the round 2-sphere.

These ideas can also be applied to the understanding of Finsler metrics on the 2-sphere whose Finsler-Gauss curvature is constant, as will be explained in the talk. This leads, via the recent work of LeBrun and Mason, to a resolution of a basic problem in Finsler geometry: to describe such Finsler metrics on the 2-sphere.

In this talk, no knowledge of Finsler geometry will be assumed, only a very basic understanding of curves and surfaces. The history of the problem will be discussed and numerous examples will be given to illustrate the underlying ideas.
 
February 20, 2009
Daniel Bienstock
Columbia University		 Recent Results on Lifted Formulations for Integer Programs
Disjunctive programming is a classical technique for 0-1optimization in which a set of vertices of the hypercube is approximated by the convex hull of (carefully selected) polyhedra. Through the work of Lovasz, Schriver, Sherali and Adams, and others, this can be tied with the idea of 'lifting' a formulation to a higher dimensional space, again by carefully choosing additional variables.

In this talk we will first provide an overview of this subject, and then describe a new use of this idea which leads to an approximation algorithm to the "minimum" knapsack problem:

s.t.

 min \sum_j c_j x_j s.t. \sum_j a_j x_j >= b (*) x_j = 0 or 1, for all j

(*)

We show that for each fixed error 0 < ε < 1, there is a polynomial-time algorithm that produces a 0 - 1 vector satisfying constraint(*), whose value is at most a factor of (1 + ε) larger than the optimum. Furthermore, this approximation is obtained by rounding the solution to a linear program. This is the first such algorithm. If time permits, we will show generalizations of this result. Joint work with Ben McClosky.
 
November 21, 2008
Frank Vallentin
Centrum Wiskunde & Informatica, Amsterdam		 Fourier Analysis, Linear Programming, and Densities of Distance Avoiding Sets
In this talk I will consider the problem of determining the maximum density of sets in Euclidean space which avoid some given distances, in the sense that there are no two points in the set at the given distances. To find upper bounds for the maximum density we use the Fourier coefficients of the autocorrelation function of the characteristic function of a distance avoiding set together with linear programming. This method is a continuous analog of the sphere packing bound due to Cohn and Elkies. I will show two applications of the bound: Computing new upper bounds for the density of sets avoiding the unit distance in dimension 2,...,24. Giving an alternative, quantitative, and extremely simple proof of a result of Furstenberg, Katznelson, Weiss, proved by ergodic theoretic methods: Every planar set of positive density does not avoid arbitrary large distances. This is joint work with Fernando M. de Oliveira Filho.  
 
November 7, 2008
Alejandro Adem
University of British Columbia		 Commuting Matrices and Spaces of Homomorphisms
Let G denote a Lie group, and consider the space of all commuting n-tuples of elements in G. In this talk we will discuss basic topological properties of spaces such as these, and how they relate to bundle theory, group cohomology and other interesting topological invariants. Examples will be provided to illustrate these connections, in particular we will describe the space of commuting pairs of elements in SU(2). The methods used will be elementary applications of topology and representation theory.  
 
October 10, 2008
Yuval Peres
Microsoft Research		 Hex, Random Turn Games, and the Infinity Laplacian
The game of Hex has two players who take turns placing stones of their respective colors on the hexagons of a rhombus-shaped hexagonal grid. Black wins by completing a crossing between two opposite edges, while White wins by completing a crossing between the other pair of opposite edges. Although ordinary Hex is famously difficult to analyze, we find that Random-Turn Hex--in which players toss a coin before each turn to decide who gets to place the next stone--has a simple optimal strategy, related to percolation. "Tug of war" is a two player random-turn game played as follows: Given disjoint target sets T1 and T2 in the plane, and a token at x, toss a fair coin; the player who wins the coin toss moves the particle up to distance r in the direction of his/her choice. This is repeated until the token reaches a target set Ti and player i is then declared the winner. Write ur(x) for the probability that player 1 wins when both players play optimally. We show that as r tends to 0, the functions ur(x) converge to the infinity harmonic function with boundary conditions 1 on T1 and 0 on T2. Our analysis of tug of war leads yields new estimates, and significant generalizations, of several classical results about infinity Laplacians. I will also describe a variant that yields p-harmonic functions for 1 < p < ∞.
 
(Talk based on joint works with Oded Schramm, Scott Sheffield and David Wilson.)  
 
The University of Washington is committed to providing access, equal opportunity and reasonable accommodation in its services, programs, activities, education and employment for individuals with disabilities. To request disability accommodation, contact the Disability Services Office at least ten days in advance at: 206-543-6450/V, 206-543-6452/TTY, 206-685-3885/FAX, or dso@u.washington.edu.