Series: Penn State Logic Seminar
Date: Tuesday, March 27, 2001
Time: 2:30 - 3:20 PM
Place: 316 Willard Building
Speaker: Martin F"urer, Computer Science, Penn State
Title: Graph Coloring, Games, and Logic
Abstract:
The graph isomorphism problem asks to determine the computational
complexity of testing whether two given finite graphs are isomorphic.
In particular, one wants to know natural classes of graphs allowing
polynomial time isomorphism tests. I will talk about the close
connection between three seemingly different tools that have helped to
understand the limited success of combinatorial approaches to the
graph isomorphism problem. The three tools are: Weisfeiler-Lehman
k-tuple refinement, a very natural combinatorial approach to the graph
isomorphism problem; a version of Ehrenfeucht-Fraisse games of finite
model theory; first order logic with counting-quantifiers restricted
to a fixed number of distinct variables.