Friday, January 24, 2003


Next week I will go away on vacation. When I go on a real vacation I go cold turkey on the Internet. No new posts or responses to comments or email until I return.

Have a great week everyone and I will see you in February.

An Efficient Algorithm for Testing whether a Graph is Perfect

Last year we saw the resolution of the Strong Perfect Graph Conjecture, a major result in graph theory. The conjecture stated that a graph is perfect if and only if it does not contain an induced subgraph H such that H or its complement is an odd cycle of length at least five. Chudnovsky, Robertson, Seymour, and Thomas proved the conjecture (now called the Strong Perfect Graph Theorem) last spring. Vašek Chvátal has a web page describing this result.

Why am I mentioning this result here? The problem of testing whether a graph is perfect in polynomial-time remained open even after this theorem as neither characterization gives an obvious algorithm. I just saw the the abstract of a talk that Paul Seymour will give at the Institute of Advanced Study next week. There he claims he and Chudnovsky have found a polynomial-time algorithm for testing whether a graph is perfect. I cannot find more about the algorithm on the web and I will miss the talk at the institute. I will post more information about this exciting new development when I have more details.

Thursday, January 23, 2003

The Lambda Calculus, Part 1

One cannot celebrate Alonzo Church, part of our Celebration of Geniuses without talking about his creation, the Lambda Calculus, a way to describe functions and functional evaluation with a very simple description and incredible power.

As an example, consider the square function, square(x)=x*x. Suppose we don't care about the name and just want to talk about the function in the abstract. The lambda calculus gives us the syntax for such discussions. We express the square function as

This is a function that takes one argument and returns its square. For example
λx.x*x(5) = 25
Also note that the use of x is not important. The following is also the square function.
So now let us formally define the syntax of the Lambda Calculus. The alphabet consists of an infinite list of variables v0, v1, the abstractor "λ", the separator "." and parentheses "(" and ")". The set of lambda terms is the smallest set such that
  1. Every variable is a lambda term.
  2. If M is a lambda term then (λx.M) is a lambda term.
  3. If M and N are lambda terms then MN is a lambda term.
We will sometimes leave off parentheses when the meaning is clear. Examples of lambda terms are xx, λx.xx, λx.λy.yx.
Free variables are those not closed off by a λ. For example in λy.xy the variable x is free and y is bound.

We use the notation M[x:=E] means replace every occurrence in the lambda term M of the free variable x by the lambda term E. There should not be any free variables in E that are bound in M as