Hugo Nobrega
(ILLC)
Characterizations by Nice Forbidding Sets
November 2nd at 17:30, in Science Park D1.113
Graphs are structures which crop up in many areas of Mathematics and have many applications, perhaps because they are an elegant and intuitive model of the ubiquitous notion of relation. For this reason, of course, they are also relevant to Logic in many different ways (e.g., in Kripke semantics for Modal Logic).
One of the common ways of characterizing a class of graphs is by a forbidden set, i.e., via a statement of the form "A graph is in the class C iff it does not contain any of the graphs in the set F", according to some precise definition of containment. In fact, such characterizations also make sense in a much broader context than just Graph Theory, but in the most general case the forbidden sets are not very interesting, and do not seem to lend themselves to any applications. When these characterizations are sought, we are really interested in "nicer" forbidden sets -- ones that contain some structural information about the class they characterize, which may then help us solve problems that are otherwise hard.
In this talk, whose aim is to be accessible to anyone with some interest (even if little experience) in Graph Theory and/or Combinatorics in general, we will make a lighthearted survey of the nice properties that may (or may not) be demanded of forbidden sets for graphs with their usual partial orders of subgraphs, induced subgraphs, and minors. Depending on the kinds of graphs and on the partial order that one considers, some interesting and large discrepancies appear. For instance, every class of finite graphs closed under minors has a finite forbidden set, but this is false for uncountably infinite graphs. Furthermore, for finite graphs with the subgraph relation, not only is this false, but actually the problem of deciding whether a class has a finite forbidden set is undecidable!