Department
Home Page
About Us:
• Contact Info.
• Faculty
• Staff
• Teaching Assistants
Academic Program:
• Admission
• Undergraduate
• Graduate
• Certificates
Courses:
• Course Description
• Class Web Pages
• Class Syllabi
Research:
• Colloquium
• Interdisciplinary Seminar
• Seminars
• Steve Goldman Lectures in Mathematical Physics
Links:
| • Completing Online GEP Courses |
| • Best Jobs |
| • Newsletter |
| • Math Lab |
| •Math Placement Test |
| • Careers |
| • American Mathematical Society |
| • Mathematical Association of America |
03/08/05 Colloquium
Dr. Neil Robertson
Ohio State University
Ohio State University
A view of graph minor theory
Abstract: Graph minors are generated from subgraphs by contracting edges. The theory of graph minors grew out of two sources, excluded minor theorems and the theory of well-quasi-order (WQO). Classical theorems are Menger's disjoint paths theorem (1927), Kuratowski's planar graph theorem (1930) and Kruskal's tree WQO theorem (1960). A WQO is a reflexive and transitive relation (Q,<=) which is well- founded and has no infinite subset of pairwise unrelated elements. Between 1981 and 1985 Seymour and Robertson showed that graphs are a WQO under minor containment, settling a question of Wagner from 1960 in a series of 20 papers. This lecture will discuss some of the open problems in the area of the same order of difficulty in both graph and matroid theory. As with graph minors these involve structure theorems, extensions of WQO theory and some computational complexity issues.