Title: Well-quasi-ordering for Tournaments
Speaker: Brenda Latka, DIMACS, Rutgers University
Date: Monday, November 24, 2003, 1:10 pm
Location: Hill Center, Room 525, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Tournament embedding defines a quasi-ordering on the class of tournaments. The class of all tournaments is not well-quasi-ordered; it contains an infinite antichain. But some subclasses of tournaments defined by forbidden subtournaments are wqo. It can be shown non-constructively that there is an algorithm to determine which forbidden subtournaments define wqo classes. Much more information, and Kruskal's Theorem, yields a constructive proof.