# Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
|
locations | Term schedule | history
|

# 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

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

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