Monday, December 5, 2011
Humboldt-Universität zu Berlin
Erwin-Schrödinger-Zentrum
Rudower Chausse 26
12489 Berlin - Adlershof
room 0'310
Lecture - 14:15
Abstract:
Acyclicity criteria in graphs and hypergraphs
can play a central role in their combinatorial and algorithmic
analysis (as well as in the model-theoretic analysis).
For graphs or hypergraphs that do possess cycles, one may
eliminate such cycles in suitable coverings.
The simplest way to achieve this involves the passage to
natural tree unfoldings. In general, acyclic coverings will
necessarily be infinite; so, if we want to stick to finite coverings,
relaxations of full acyclicity need to be considered. In the case of graphs,
simple and uniform group-based constructions lead to finite coverings that
do not have any short cycles, and therefore are locally acyclic.
The situation for hypergraphs is much trickier.
The natural hypergraph analogue of graph acyclicity
is tree-decomposability. It is not hard to see, however,
that even local tree-decomposability cannot be achieved in finite coverings in
general. The goal to construct coverings that guarantee alternative
measures of acyclicity in hypergraphs, therefore, is an interesting
combinatorial challenge.
In this talk I shall introduce the relevant notions
and report on recent progress along these lines.
Related combinatorial results involve, for instance, a strong
generalisation of the concept of large girth for Cayley groups
and novel constructions of such groups and of homogeneous hypergraphs
of correspondingly controlled acyclicity.
Colloquium - 16:00
Abstract:
Let f be a uniformly distributed random k-SAT formula with n variables and m clauses. Non-rigorous statistical mechanics ideas have inspired a message passing algorithm called Belief propagation guided decimation for finding satisfying assignments of f. This algorithm can be viewed as an attempt at implementing a certain thought experiment that we call the decimation process. In this work we identify a variety of phase transitions in the decimation process and link these phase transitions to the performance of the algorithm. This is joint work with Amin Coja Oghlan.