MSI Weekly Bulletin - Week starting Monday 23 October, 2006

A matching M of a graph G is a set of independent edges (i.e. no two edges of M share a common vertex). A matching M of a graph G is k-separated if the minimum distance between an end-point of an edge in M and an end-point of another edge in M is at least k in G. Let MkM denote the problem of finding a maximum k-separated matching of a graph (i.e. a k-separated matching with the greatest possible number of edges). When k=1, this is just a matching in the classical sense. When k=2, a 2-separated matching is also referred to as an induced matching. M2M has applications in channel assignment, VLSI design and network flow problems. It is also related to finding the strong-edge-chromatic index of a graph. However, for k>1, MkM is known to be NP-hard, even if k=2 and the graphs considered are bipartite with maximum degree 4. Recently, algorithms for approximating MkM have received much attention. In this talk we will first give a brief overview of some known results. We will then examine greedy algorithms for approximating MkM when the graphs considered are random and d-regular (i.e. all vertices have degree d). In particular, we will consider MkM when k>2.

In this talk I will start with introducing basic concepts of model category theory. After discussing some examples and techniques we will introduce the concept of homotopical localization. This talk is aimed to a general audience.

In this talk we will go through a paper of Keller and Blank from 1951, looking at the problem of a plane pulse striking a corner. They employ some clever changes of coordinates to determine the solution analytically.

High resolution X-ray diffraction crystallography is now capable of resolving anisotropic atomic motions in biological macromolecules such as proteins and DNA. This information is included in Protein Data Bank records in the form of "anisotropic temperature factors", which summarize uncertainty in atomic positions due to thermal and lattice vibrations as a variance-covariance matrix. From a theoretical viewpoint, proteins are also studied with molecular dynamics simulations using empirical force fields. A question of interest to theoretical biochemists is: How can we compare estimates of anisotropic temperature factors from molecular dynamics simulations with experimental measurements from X-ray diffraction data. In this talk I will describe a compact graphical technique we have developed for assessing agreement between theory and experiment in a way which is meaningful to biochemists. No prior knowledge of biochemistry or bioinformatics will be assumed in this talk.