#
Monday Lecture and Colloquium

**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**

###
Mihyun Kang - Humboldt Universität zu Berlin

###
Enumerative methods

*Abstract:*

We discuss the following enumerative methods:

- Classical methods
- Recursive method
- Generating function and singularity analysis
- Gaussian matrix integral

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**

###
Isolde Adler - Humboldt Universität zu Berlin

###
Tree decompositions and the homomorphism problem

*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.

Letzte Aktualisierung:
08.12.2006