Abstract: We present an All-Pairs Shortest Paths (APSP) algorithm whose expected running time on a complete directed graph on n vertices whose edge weights are chosen independently and uniformly at random from [0, 1] is O(n²). This resolves a long standing open problem. The algorithm is a variant of the dynamic all-pairs shortest paths algorithm of Demetrescu and Italiano. The analysis relies on a proof that the expected number of locally shortest paths in such randomly weighted graphs is O(n²). We also present a dynamic version of the algorithm that recomputes all shortest paths after a random edge update in O(log² n) expected time.

Abstract: More than twenty years ago, Manickam, Miklos, and Singhi conjectured that for any integers n ≥ 4k, every set of n real numbers with nonnegative sum has at least (n - 1 choose k - 1) k-element subsets whose sum is also nonnegative. In this talk we discuss the connection of this problem with matchings and fractional covers of hypergraphs, and with the question of estimating the probability that the sum of nonnegative independent random variables exceeds its expectation by a given amount. Using these connections together with some probabilistic techniques, we verify the conjecture for n ≥ 33k². This substantially improves the best previously known exponential lower bound on n.

If time permits we will also discuss applications to finding the optimal data allocation for a distributed storage system and how our approach can be used to prove some theorems on minimum degree ensuring the existence of perfect matchings in hypergraphs.

Abstract: Given a fixed positive integer r and a fixed graph F, we consider for host-graphs H on n vertices, n large, the number c_r,F(H) of r-colorings of the set of edges of H such that no monochromatic copy of F arises. In particular, we are looking at the maximum c_r,F(n) of c_r,F(H) over all host-graphs H on n vertices. For forbidden fixed complete graphs F = K_ℓ the quantity c_r,F(n) has been investigated by Yuster, and Alon et al. and they proved for r = 2 or r = 3 colors that the maximum number of r-colorings is achieved by the corresponding Turán graph for F, while for r ≥ 4 colors this does not hold anymore. Based on similar results for some special forbidden hypergraphs, one might suspect that such a phaenomenon holds in general.

Abstract: Cops and robbers - in theory almost as thrilling as in an action film. The game was introduced by Nowakowski and Winkler, and by Quilliot more than thirty years ago: A number of cops moves along the edges of a graph and try to catch the robber. First, the cops move (at most) one step, then the robber. The cop number c(G), introduced by Aigner and Fromme in 1982, is the minimal number of cops needed in G in order to catch the robber. Numerous questions connected with this game have been posed and partly answered:

What kind of graphs can be covered by one cop alone (the so-called cop-win graphs)?

How many cops are enough to catch the robber on a planar graph?

What can we say about graphs embeddable in orientable surfaces of genus g?

How many cops do you need/are enough on general graphs?

Variations include a drunken robber (who moves randomly, and not in an intelligent way), a very fast robber (who may move along longer paths in one step), and non-perfect information.

Abstract: In 1879/80 Andrei A. Markoff studied the minima of indefinite quadratic forms and found an amazing relationship to the Diophantine equation x² + y² + z² = 3xyz, which today is named the Markoff equation. Later Georg Frobenius conjectured that each solution of this equation is determined uniquely by its maximal component. Defining these components as the so-called Markoff numbers this conjecture means that for each Markoff number m there exists up to permutation exactly one triple (m, p, q) with maximum m solving the Markoff equation.

Till this day it is not known whether the conjecture is true, or not. However, we are able to prove uniqueness for certain Markoff numbers and we can find different statements, such as a statement in Markoff's theory on the minima of quaratic forms, being equivalent to the uniqueness conjecture of the Markoff numbers.

At first I will give a short overview on the properties of Markoff numbers as well as some easier results concerning the uniqueness conjecture. We will see how the solutions of Markoff's equation, called Markoff triples, can be computed recursively such that we will get a tree of infinitely many Markoff triples. Then, by using correspondences to other trees we will get different statements from Number Theory, Graph Theory and Linear Algebra being equivalent to the uniqueness conjecture.

Abstract: Construct a random m × n matrix by independently setting each entry to 1 with probability p and to 0 otherwise. We study the joint distribution of the row sums s = (s₁, ..., s_m) and column sums t = (t₁, ..., t_n). Clearly s and t have the same sum, but otherwise their dependencies are complicated. We prove that under certain conditions the distribution of (s, t) is accurately modelled by (S₁, ..., S_m, T₁, ..., T_n), where each S_j has the binomial distribution Binom(n, p'), each T_k has the binomial distribution Binom(m, p'), p' is drawn from a truncated normal distribution, and S₁, ..., S_m, T₁, ..., T_n are independent apart from satisfying Σ_j=1,...,m S_j = Σ_k=1,...,n T_k. We also consider the case of random 0-1 matrices where only the number of 1s is specified, and also the distribution of s when t is specified. In the seminar I will include details of one of the bounding arguments used in this last case. This bounding argument is an application of the generalised Doob's martingale process.

These results can also be expressed in the language of random bipartite graphs.

Abstract: Policy iteration is one of the most important algorithmic schemes for solving problems in the domain of determined game theory such as parity games, stochastic games and Markov decision processes, and many more. It is parameterized by an improvement rule that determines how to proceed in the iteration from one policy to the next. It is a major open problem whether there is an improvement rule that results in a polynomial time algorithm for solving one of the considered game classes.

Abstract: Given a (di)graph H and an integer q ≥ 2, the size Ramsey number r_e(H, q) is the minimal number m for which there is a (di)graph G with m edges such that every q-coloring of G contains a monochromatic copy of H. We study the size Ramsey number of the directed path of length n in oriented graphs, where no antiparallel edges are allowed. We give nearly tight bounds for every fixed number of colors, showing that for every q ≥ 2, the corresponding number r_e(H, q) has asymptotic order of magnitude n^{2q - 2 + o(1)}.