Graph Coloring, Games, and Logic

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.