DIMACS Graduate Student Combinatorics Seminar Series

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


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.