January 8, 2007
Humboldt-Universität zu Berlin
Institut für Informatik
Rudower Chaussee 25
12489 Berlin
Humboldt-Kabinett, 1st floor, between house III and IV
Lecture - 14:15
Abstract:
We discuss the following enumerative methods:
Classical methods for the enumeration of combinatorial structures
include induction, bijection, and decomposition. For the enumeration of
graphs, we decompose graphs, in particular, along the connectivity,
which yields a decomposition tree. The recursive method derives
recursive counting formulas according to the decomposition tree, from
which we compute the exact numbers and design a uniform sampling
algorithm to generate a graph as a reversed procedure of the
decomposition. Furthermore, we interpret the decomposition in terms of
generating functions. Using singularity analysis we determine the
dominant singularities of generating functions and their singularity
types, from which we estimate the asymptotic numbers. Using the
asymptotic numbers and the probabilistic method we investigate typical
asymptotic properties of random structures. On the other hand,
theoretical physicists use Gaussian matrix integral of Hermitian
matrices to enumerate graphs embedded on a 2-dimensional surface. In
this talk we illustrate the enumerative methods using planar structures,
such as trees and planar graphs.
Colloquium - 16:00
Abstract:
The homomorphism problem (HOM) asks for given relational structures A and B
whether there is a homomorphism from A to B.
HOM is NP-complete in general, and it becomes tractable when restricted to instances
A, B where A has bounded tree-width (hypertree-width, fractional hypertree-width).
We generalise the homomorphism problem to structures possibly containing partial
functions, and we introduce tree-width notions for graphs and hypergraphs that may
contain directed edges. These notions make use of the fact that we can quickly compute
the value of a partial function, and they give rise to larger classes of tractable
instances of HOM.