Forschungsseminar

Fortsetzung des Vortrages vom 5.12.

Im Vortrag wird ein Überblick über Property Testing auf Expansion in gradbeschränkten Graphen gegeben, basierend auf den papers von Goldreich&Ron, Czumaj&Sohler und Nachmias&Shapira.

Which properties $P$ are such that every object satisfying $P$ "behaves" like a truly random one? In the context of graph the systematic study of this question was initiated by Thomason and in a cornerstone contribution Chung, Graham, and Wilson gave a long list of such properties which turned out to be equivalent. This settled the notion of quasi-random graphs. In this talk we will focus on uniform hypergraphs. In particular, I will point out some connections between quasi-random hypergraphs and Weak Regularity Lemma. This is a joint work with David Conlon, Yury Person, and Mathias Schacht.

For a graph H the F-packing number is the maximum number of edge disjoint copies of the graph F in H. It is well known that computing this number is NP-hard if F contains a component with at least 3 edges. A result of Haxell and Rödl shows that the packing number can be approximated by the fractional packing number up to an additive error term of order o(n^2), n being the number of vertices of H. Since the fractional packing number can be calculated using linear programming, this provides an efficient approximation algorithm for the (integer) packing number. However, the error term is only meaningful if H is dense, i.e. has $Omega(n^2)$ edges, since the fractional packing number is bounded from above by e(H)/e(F). We discuss a probabilistic version of this result for subgraphs of the binomial random graph G(n,p). More precisely, we show that for p=p(n) larger than a certain function p_F(n)=o(1) with high probability for all subgraphs H of G(n,p) the F-packing number of H can be approximated up to an error term of o(pn^2). The proof is based on the application of the sparse regualarity lemma and a result of Frankl and Rödl concerning nearly perfect matchings in uniform hypergraphs.

Bei der Entwicklung von Algorithmen für Graphenprobleme wird standardmäßig das RAM-Modell zugrunde gelegt. Dieses Modell unterstellt einen wahlfreien Zugriff (random access) auf den Eingabegraphen und eine unbeschränkte Arbeitsspeichergröße. Allerdings sind diese Annahmen unrealistisch bei der Behandlung von riesigen Graphen, die nicht in gängige Arbeitsspeicher passen und nur auf externen Speichern wie Festplatten oder Magnetbändern vorräting gehalten werden können. Zur Modellierung dieser Umstände hat Muthukrishnan 2003 das Semi-Streaming Modell vorgeschlagen, welches obige Annahmen des RAM-Modells fallen lässt: Die Eingabe für einen Semi-Streaming Algorithmus besteht aus einem Datenstrom von Kanten eines Graphen in beliebiger Reihenfolge. Der Arbeitsreicher ist beschränkt, so dass die Speicherung des kompletten Graphen nicht möglich ist. In diesem Vortrag führe ich das Modell und seine wesentlichen Parameter ein. Dann werden Semi-Streaming Algorithmen vorgestellt, die grundlegende Graphenprobleme wie die Berechnung des Zusammenhangs oder eines minimal spannenden Baumes lösen. Interessanterweise erreichen diese Algorithmen die gleichen asymptotischen Laufzeiten wie die entsprechenden Algorithmen im ungleich mächtigeren RAM-Modell. Wir werden sehen, warum das Finden eines minimalen Schnittes in einem Graphen nicht möglich ist. Schließlich stelle ich für die Berechnung einen schwersten Matchings, einem Problem, dass nicht exakt lösbar ist, den besten bekannten Approximationsalgorithmus vor.

Die Regularitätsmethode für Graphen wurde vor ca. 30 Jahren von Szemeredi, für den Beweis seines Dichteresultates über Teilmengen der natürlichen Zahlen, welche keine arithmetischen Progressionen enthalten, entwickelt. Grob gesprochen besagt das Regularitätslemma, dass die Knotenmenge eines beliebigen Graphen in konstant viele Klassen zerlegt werden kann, so dass fast alle induzierten bipartiten Graphen quasi-zufällig sind, d.h. sie teilen sich viele Eigenschaften mit zufälligen bipartiten Graphen derselben Dichte. Das Regularitätslemma hatte viele weitere Anwendungen, vor allem in der extremalen Graphentheorie, aber auch in der theoretischen Informatik und der kombinatorischen Zahlentheorie, und gilt mittlerweile als eines der zentralen Hilfsmittel in der modernen Graphentheorie. Vor wenigen Jahren wurde das Regularitätslemma für andere diskrete Strukturen entwickelt. Insbesondere wurde die Regularitätsmethode für uniforme Hypergraphen verallgemeinert. In diesem Vortrag werde ich die neuesten Entwicklungen der Regularitätsmethode für Hypergraphen diskutieren und einige Anwendungen vorstellen. Im Besonderen werden wir sehen, dass hereditäre (entscheidbare) Hypergrapheneigenschaften, das sind Familien von Hypergraphen, welche unter Isomorphie und induzierten Untergraphen abgeschlossen sind, testbar sind. D.h. es existiert ein randomisierter Algorithmus, der in konstanter Laufzeit mit hoher Wahrscheinlichkeit zwischen Hypergraphen, welche die Eigenschaft haben und solchen die "weit" davon entfernt sind, unterscheidet.

We consider two variants of the Parallel Repetition technique. The first obtains a connection between the expansion properties of the input instance and the amplification rate. Namely, we show that a $(1-varepsilon)$ satisfiable instance yields an instance which is at most $(1-varepsilon)^{tilde{Omega }(gamma)cdot k}$ satisfiable, where $k=O(frac1{varepsilon})$ is the repetition parameter and $gamma$ is the spectral-gap of the input instance. This variant maintains the uniqueness property of the constraints. We compare this analysis to a corresponding lower bound on the success probability, obtained by extending [Raz08] to large instances of relatively large spectral-gap. In the second variant of the Parallel Repetition technique we obtain an optimal amplification, regardless of the spectral-gap $gamma$, namely $(1-varepsilon)^{{Omega }(k)}$, again for $k=O(frac1varepsilon)$. However this variant does not maintain the uniqueness property. The technique can also be used as a generalizing tool for converting approximation algorithm that is tuned for one set of parameters (error, size of alphabet and approximation ratio) into an approximation algorithm for other parameters. This is joint work with S. Safra.

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.