Forschungsseminar

Ranking algorithm that are purely based on link-structure analysis play an important role in search engine design. While Google's famous PageRank works with a Markov-chain random-surfer model, J. Kleinbergs HITS counts a certain type of paths in the webgraph. I will show that a stochastic model of HITS can be given using a braching-process approach. Further I will give some results which state how this branching-algorithm works on an Erdös-Rényi-random-graph.

Beginning on an empty graph on 'n' vertices we add an edge vertex by vertex uniformly at random, under the condition that the maximum degree does not exceed a fixed constant 'd'. Simulations show that the size of the maximal component undergoes a dramatic change: shortly after 0.5n steps of the process it jumps to sizes of different magnitute. When does this change occur? Which are the sizes of the maximal component? This theses tries to give the respective answers by combining: the differential equation method of Wormald, the configuration model, bounding large deviations of supermartingales and measure dominance.

A streaming algorithm has no ramdom access to the input graph and a working memory that is too small to contain the whole input. We will see that for such an algorithm the exact computation of a minimum cut is intractable and how a randomized approximation of it can be achieved.

Dirac's Theorem guarantees the existence of a Hamiltonian cycles in a graph $G$ provided its minimum degree is at least $n/2$. In the talk I will speak about generalisations for $k$-uniform hypergraphs. This is a joint work with Mathias Schacht.

In 1983, Chvatal, Rödl, Szemeredi, and Trotter proved that for any D there exists B so that for any n, any 2-coloring of edges of the complete graph on N=Bn vertices yields a monochromatic copy of any graph $H$ which has $n$ vertices and maximum degree D. In this talk we prove that the complete graph on N vertices can be replaced by a sparser graph G which has N = Bn vertices and $O(N^{2-1/D}log^{1/D}N)$ edges. Consequently the size-Ramsey number of any graph H with n vertices and maximum degree D is smaller than $O(N^{2-1/D}log^{1/D}N)$. This is joint work with Y. Kohayakawa, V. Rödl and E. Szemeredi.

Szemeredi's regularity lemma states that every graph can be well approximated by randomly looking bipartite graphs. It led to many exciting applications in graph theory and in computer science. In the first part of my talk I will introduce all the relevant concepts around regularity lemma precisely. There is a straightforward generalisations to uniform hypergraphs, called weak hypergraph regularity lemma. The second part will be about recent developments in the applications of the weak hypergraph regularity lemma. Thus, the goal of the talk will be to prove(sketch. ;-)) that almost all 3-uniform hypergraphs not containing a Fano plane are bipartite. This is joint work with Mathias Schacht.

We outline a method that applies ultra-products for finite combinatorial problems. We show its relationship to the hypergraph regularity method developed by Nagle-Rödl-Schacht-Skokan and independently by Gowers. We also show a uniqueness of the structure of hypergraph regular partitions. Joint work with Gábor Elek.

A seminal technique of theoretical physics called Wick's theorem interprets the Gaussian matrix integral of the products of the trace of powers of Hermitian matrices as the number of labelled maps with a given degree sequence, sorted by their Euler characteristics. This leads to the map enumeration results analogous to those obtained by combinatorial methods. A natural question is whether the method may as well be applied to the enumeration of graphs embeddable on a given 2-dimensional surface (a main research topic of contemporary enumerative combinatorics). Martin Loebl and I recently showed that this can be done, by applying the matrix integral to combinatorially defined functions, in order to loosen the strong connection with maps implied by the integration of the functions of traces. This talk is based on joint work with Martin Loebl http://arxiv.org/abs/math/0605218.

I will give an introduction to the theory of communication complexity. After that we will see how space lower bounds for streaming computations can be concluded.

Given a hypergraph $H$ on $n$ vertices. Which degree condition guarantees the existence of a perfect matching in $H$? Recently this question was addressed by several researchers. The aim of this talk is to give a brief introduction on this topic.

A map is a graph drawn on a surface (of any genus) without edge crossings. The enumerative study of maps has been a classical topic of combinatorics and statistical physics since the sixties, and has attracted much attention in the last few years, thanks to connections with probability theory and computational geometry. This talk will be an introduction to the enumerative theory of maps on surfaces. I will focus on recent bijective techniques which reduces the enumeration of maps to the one of certain classes of trees. For example, the asymptotic behaviour of the numbers counting maps of genus g can be obtained very easily.

Den Vortrag zu Ramsey-Klassen werde ich mit einer Wiederholung der klassischen Sätze von Ramsey beginnen. Dann werde ich Ramsey-Klassen einführen und einige Beispiele näher betrachten. Es ist ein offenes Problem, ob Ramsey-Klassen klassifiziert werden koennen. Ich schliesse meinen Vortrag mit der Beobachtung von Nesetril, dass Ramsey-Klassen die Amalgamierungseigenschaft haben. Diese Beobachtung erlaubt es, Resultate aus der Modelltheorie für die Klassifikation von Ramsey-Klassen zu verwenden.

The differential equation method is a useful method for studying certain random variables defined on random graph processes. In particular it can be used to find the expectations of the random variables and show that they are concentrated around their expectations. In my talk I will present the differential equation method along with some applications. I will also present a new result, saying that the differential equation method can be used to show that the random variables converge jointly to a normal distribution.

******************************************** ACHTUNG: Gesonderter Termin: Do 13.12., 15:15 ******************************************** The Loebl--Koml'os--S'os Conjecture asserts that any graph of order $n$ which has at least half of its vertices of degrees at least $k$ contains any tree with $k$ edges as a subgraph. In the talk, I shall sketch a proof of this conjecture in the case when $k$ is linear in $n$. The proof uses the Regularity lemma and combines tools developed by Piguet and Stein and by Zhao. This is a joint work with Jan Hladk'y.

*********************************************************************** ACHTUNG: Gesonderter Termin und Ort: Fr 7.12., 10:45, Humboldt-Kabinett *********************************************************************** We survey clustering algorithms for the placement problem in VLSI-design.

******************************************** ACHTUNG: Gesonderter Termin: Do 6.12., 15:15 ******************************************** In this talk we show how one can combine generating functions techniques with the framework of Boltzmann sampler algorithms and purely combinatorial approaches in order to obtain very precise information about the degree sequence of random outerplanar and series-parallel graphs. Joint work with Nicla Bernasconi and Angelika Steger.

We continue the talk from last week and focus on open questions and conjectures.

The straight forward generalization of the Szemeredi's concept of regular graphs to hypergraphs is generally believed to be of only little use, as it does not allow an accompanying "counting lemma". Such a counting lemma should assert that an appropriate collection of sufficiently "regular" block contains the right number of subgraphs of any given isomorphism type. In this talk we will discuss for which hypergraphs a counting lemma holds for the notion of weak hypergraph regularity and indicate some applications.

We introduce a general method to count and to efficiently sample random unlabeled combinatorial structures. Our method is illustrated on several examples: in each case, we provide enumerative results and efficient random samplers. The approach applies to unlabeled families of plane and non-plane unrooted trees, and tree-like structures in general, but also to cactus graphs, outerplanar graphs, RNA secondary structures, and classes of planar maps. Joint work with Eric Fusy, Mihyun Kang, and Stefan Vigerske.

A branching is a directed acyclic Graph, where each node has an in-degree of at most one. Given a directed Graph G=(V,A) with arc weights, we are interested in finding the heaviest branching which is a subgraph of G. Edmonds discovered a basic algorithm for the above problem, later Gabow et al. showed how to implement this method in O(m+nlog n) time. It can be seen that this running time is best possible for any implementation of Edmonds' algorithm. I will give an outline of the exact algorithm and show how to derive a simple approximation scheme with a linear running time.

ACHTUNG: Datum und Zeit! We consider the task of network exploration by a mobile agent (robot) with small memory. The agent has to traverse all nodes and edges of a network (represented as an undirected connected graph), and return to the starting node. Nodes of the network are unlabeled and edge ports are locally labeled at each node. The agent has no a priori knowledge of the topology of the network or of its size, and cannot mark nodes in any way. Under such weak assumptions, cycles in the network prevent feasibility of exploration, hence we restrict attention to trees. We present an algorithm to accomplish tree exploration (with return) using O(log n)-bit memory for all n-node trees. An algorithm using O(log2 n)-bit memory and an Omega(log n) lower bound were shown previously. This is joint work with Leszek Gasieniec, Andrzej Pelc and Xiaohui Zhang