Re: Saunders MacLane


I wrote:
|The audience member then proceeded to explain
|that this test for having a K5 as a subgraph and so on were
|all polynomial time tests (albeit slow) and knowing that a
|finite set of such tests sufficed showed that the problem lay
|in P, in computing complexity terms.

Dave Rusin wrote:
|I thought Carsten Thomassen showed that determining the genus of
|a graph was an NP-complete problem?

Aha! See

http://www.research.att.com/~dsj/columns/col19.pdf

I now find that the seminar took place close to the time
that Robertson and Seymour had just proven that for a
_fixed_ graph H, whether a graph G contains a subgraph
homeomorphic to H is in P. This was considered a breakthrough,
so it's not at all obvious. They also proved that for a
fixed H, determining whether a given G and given mapping of
the vertices of H to vertices of G can be extended to a
homeomorphism of H and a subgraph of G is in P. This same
column of Johnson points out that the corresponding problems
with varying H are NP complete.

It had been a few years since Robertson and Seymour proved
the general result that for a fixed g, there exists a finite
set of test graphs which embed homeomorphically into any graph
of genus >g.

This ties up some ancient loose threads that I hadn't even
known were loose. A few years later, I was living in a
basement apartment in the house of Richard Anstee, a
combinatorist. One day I saw a paper of his appear, in
which he referred to the Robertson-Seymour results, and
exclaimed "Wow!" I told him it wasn't often I saw "wow" in
a published paper. He said it was based on a talk he gave,
but that these were indeed remarkable results. I didn't know
until today that there was any connection.

Keith Ramsay

.

Relevant Pages