Monday, December 5, 2011
Humboldt-Universität zu Berlin
Rudower Chausse 26
12489 Berlin - Adlershof
Lecture - 14:15
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
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.