Chaire Aisenstadt 2006-2007 Aisenstadt Chair
Professor Paul Seymour (Princeton University) Une série de conférences / A series of lectures "Structure theorems in graph theory" Fix a graph H. What is the most general graph that does not contain H? In other words, how do we explicitly construct all the graphs that do not contain H ? To begin to make this precise, we have to say what "contain" means; we have in mind either minor containment, or induced subgraph containment. But what do we mean by an "explicit construction" of a class of graphs? We give some examples, describe some connections and differences between the two containment relations, and discuss several open questions in the area. There will be no detailed proofs, and very little knowledge of graph theory will be assumed. Cette conférence s'adresse à un large auditoire. / Suitable for a general audience. Le lundi 11 décembre 2006 / Monday, December 11, 2006 16 h / 4:00 pm Université de Montréal Pavillon André-Aisenstadt, 2920, ch. de la Tour Salle / Room 1140
Une réception suivra la conférence au Salon Maurice-l'Abbé, Pavillon André-Aisenstadt (Salle 6245). There will be a reception after the lecture in Salon Maurice-l'Abbé, Pavillon André-Aisenstadt (Room 6245). "Induced subgraph testing" How hard is it to test whether an input graph has an induced subgraph in some fixed family of graphs? This depends on the family, but there are very few nontrivial families for which a polynomial-time algorithm is known. We survey some of these.
In particular, what about testing whether the input graph contains a "theta" (an induced subgraph consisting of two nonadjacent vertices joined by three vertex-disjoint paths). For instance, line graphs do not contain thetas, so the question is not trivial. Indeed, this has been an open question of some interest since a number of very similar questions are known to be NP-complete. We now have a polynomial-time algorithm. The algorithm consists of a number of applications of a subroutine to test whether three given vertices are in an induced tree. So when are three given vertices in such a tree? This question in turn has a surprisingly neat answer; there is a structural characterization of the graphs in which no such tree exists (the graph has to admit a sort of generalized line graph structure), and we can test for this structure. Joint work with Maria Chudnovsky (Columbia University). Le mercredi 13 décembre 2006 / Wednesday, December 13, 2006 16 h / 4:00 pm Université de Montréal, Pavillon André-Aisenstadt 2920, ch. de la Tour Salle / Room 6214 "The Caccetta-Häggkvist conjecture" This conjecture is a well-known open problem dating from 1978. In its simplest form, it asserts that for any integer k > 0, if G is a directed graph without parallel edges, and every vertex has outdegree at least |V(G)|/k, then there is a directed cycle of length at most k. This is easy for k = 1,2, but for k = 3 is still open. This talk will be a survey of the problem and of our recent work on it: related conjectures, partial results, approaches and counterexamples. Joint work with Maria Chudnovsky and Blair Sullivan. Le vendredi 15 décembre 2006 / Friday, December 15, 2006 14 h / 2:00 pm Université de Montréal Pavillon André-Aisenstadt, 2920, ch. de la Tour Salle / Room 6214 |