Combinatorics Seminar 2010/2011
Archive of old talks. The current schedule can be found here.
Date  Speaker  Title 

13.07.2011  Kevin Milans University of South Carolina 

06.07.2011  Uri Zwick Tel Aviv University 
AllPairs Shortest Paths in O(n^{2}) Expected Time 
29.06.2011  Benny Sudakov UCLA 
Nonnegative ksums, fractional covers, and probability of small deviations 
22.06.2011  Hanno Lefmann TU Chemnitz 
Edge Colorings of Graphs and Fixed Forbidden Monochromatic Subgraphs 
15.06.2011  Anita Liebenau FU Berlin 
A survey on the 'Copsandrobbers problem' 
09.06.2011  Endre Szemerédi Rényi Institute of Mathematics 
Long Arithmetic Progression in Sumsets 
20.05.2011  Timothy Gowers University of Cambridge 
A combinatorial proof of the density HalesJewett theorem 
13.05.2011  Dan Spielman Yale University 
On some problems that have been bugging me 
12.05.2011  Dennis Clemens FU Berlin 
The uniqueness conjecture of Markoff numbers and equivalent problems: Part II 
04.05.2011  Dennis Clemens FU Berlin 
The uniqueness conjecture of Markoff numbers and equivalent problems: Part I 
24.02.2011  Fiona Skerman Australian National University 
Row and column sums of random 01 matrices 
23.02.2011  Katherine Edwards McGill University 
Packing Tjoins in Planar Graphs 
16.02.2011  Oliver Friedman LMU München 
On Exponential Lower Bounds for Solving Infinitary Payoff Games and Linear Programs: Part II 
28.01.2011  Dmitry Shabanov Moscow State University 
The Problem of Erdős and Hajnal Concerning Colorings of Hypergraphs and its Generalizations 
21.01.2011  Tibor Szabó FU Berlin 
The Local Lemma is tight for SAT II 
14.01.2011  Tibor Szabó FU Berlin Gábor Tardos Rényi Institute of Mathematics 
The Oberwolfach Problems 
17.12.2010  Tibor Szabó FU Berlin 
The Local Lemma is tight for SAT 
10.12.2010  Yury Person FU Berlin 
Extremal Hypergraphs for Hamilton Cycles 
03.12.2010  Michael Krivelevich Tel Aviv University 
The Size Ramsey Number of a Directed Path 
04.10.2010  26.11.2010  (Pre)DocCourse 
Abstracts:
06.07.2011 

Uri Zwick (Tel Aviv University) 
AllPairs Shortest Paths in O(n^{2}) Expected Time 
Abstract: We present an AllPairs 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^{2}). This resolves a long standing open problem. The algorithm is a variant of the dynamic allpairs 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^{2}). We also present a dynamic version of the algorithm that recomputes all shortest paths after a random edge update in O(log^{2} n) expected time. Joint work with Yuval Peres, Dmitry Sotnikov and Benny Sudakov. 
29.06.2011 

Benny Sudakov (UCLA) 
Nonnegative ksums, fractional covers, and probability of small deviations 
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) kelement 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^{2}. 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. Joint work with N. Alon and H. Huang, last part is also joint with P. Frankl, V. Rodl and A. Rucinski. 
22.06.2011 

Hanno Lefmann (TU Chemnitz) 
Edge Colorings of Graphs and Fixed Forbidden Monochromatic Subgraphs 
Abstract: Given a fixed positive integer r and a fixed graph F, we consider for hostgraphs H on n vertices, n large, the number c_{r,F}(H) of rcolorings 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 hostgraphs 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 rcolorings 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. However, it seems this is not valid for (at least some) classes of forbidden bipartite graphs. 
15.06.2011 

Anita Liebenau (FU Berlin) 
A survey on the 'Copsandrobbers problem' 
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 socalled copwin 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 nonperfect information. In the talk, I will define all necessary concepts, and give an overview of what has been done in these last three decades. Further, I will sketch a proof by Scott and Sudakov (2011) of one of the most recent upper bounds on c(G). 
09.06.2011 

Endre Szemerédi (Rényi Institute of Mathematics) 
Long Arithmetic Progression in Sumsets 
Abstract: We are going to give exact bound for the size of longest arithmetic progression in sumset sums. In addition we describe the structure of the subset sums and give applications in number theory and probability theory. (this part is partially joint work with Van Vu) 
04.05.2011, 12.05.2011 

Dennis Clemens (FU Berlin) 
The uniqueness conjecture of Markoff numbers and equivalent problems 
Abstract: In 1879/80 Andrei A. Markoff studied the minima of indefinite quadratic forms and found an amazing relationship to the Diophantine equation x^{2} + y^{2} + z^{2} = 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 socalled 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. The second part of my presentation will be concerned with the best known result on this conjecture proven by J. O. Button in 2001. With a bijection between Markoff triples and elements in certain number fields we will see how the uniqueness problem can be reformulated as a question in Ideal Theory. Taking results on ideals and continued fractions we finally can conclude a criterion proving uniqueness for a big subset of Markoff numbers. 
24.02.2011 

Fiona Skerman (Australian National University) 
Row and column sums of random 01 matrices 
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_{1}, ..., s_{m}) and column sums t = (t_{1}, ..., 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_{1}, ..., S_{m}, T_{1}, ..., 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_{1}, ..., S_{m}, T_{1}, ..., T_{n} are independent apart from satisfying Σ_{j=1,...,m} S_{j} = Σ_{k=1,...,n} T_{k}. We also consider the case of random 01 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. Joint work with Brendan McKay. 
23.02.2011 

Katherine Edwards (McGill University) 
Packing Tjoins in Planar Graphs 
Abstract: Let G be a graph and T an even sized subset of its vertices. A Tjoin is a subgraph of G whose odddegree vertices are precisely those in T, and a Tcut is a cut δ(S) where S contains an odd number of vertices of T. It has been conjectured by Guenin that if all Tcuts of G have the same parity and the size of every Tcut is at least k, then G contains k edgedisjoint Tjoins. We discuss some recent progress on this conjecture and related results. 
16.02.2011 

Oliver Friedman (LMU München) 
On Exponential Lower Bounds for Solving Infinitary Payoff Games and Linear Programs: Part II 
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. Simplex algorithms for solving linear programs are closely related to policy iteration algorithms. Like policy iteration, the simplex algorithm is parameterized by a socalled pivoting rule that describes how to proceed from one basic feasible solution in the linear program to the next. Also, it is a major open problem whether there is a pivoting rule that results in a (strongly) polynomial time algorithm for solving linear programs. We describe our recent constructions for parity games that give rise to superpolynomial and exponential lower bounds for all major improvement rules, and how to extend these lower bounds to more expressive game classes like stochastic games. We show that our constructions for parity games can be translated to Markov decision processes, transferring our lower bounds to their domain, and finally show how the lower bounds for the MDPs can be transferred to the linear programming domain, solving problems that have been open for several decades. 
28.01.2011 

Dmitry Shabanov (Moscow State University) 
The Problem of Erdős and Hajnal Concerning Colorings of Hypergraphs and its Generalizations 
Abstract: The talk is devoted to the classical exremal combinatorial problem that was stated by P.Erdős and A.Hajnal in the 60s. The task is to find the value m(n, r) equal to the minimum number of edges in an nuniform nonrcolorable hypergraph. This problem has a lot of generalizations and is closely related to the classical problems of Ramsey theory. We shall discuss the known bounds in the ErdősHajnal problem, present some new results and pay special attention to the probabilistic methods, by which these results have been obtained. 
14.01.2011 

Tibor Szabó (FU Berlin) & Gabór Tardos (Rényi Institute of Mathematics) 
The Oberwolfach Problems 
Abstract: We plan to state and initiate an informal discussion on (an admittedly subjective selection of) the open problems raised in last week's Combinatorics workshop. 
21.01.2011 

Tibor Szabó (FU Berlin) 
The Local Lemma is tight for SAT II 
Abstract: I will give a construction of unsatisfiable kSAT formulas, where each variable is contained in only a few clauses. The numerical value of "few" is asymptotically best possible. Joint work with Heidi Gebauer and Gabór Tardos. 
17.12.2010 

Tibor Szabó (FU Berlin) 
The Local Lemma is tight for SAT 
Abstract: We construct unsatisfiable kCNF formulas where every clause has k distinct literals and every variable appears in at most (2/e + o(1))2^{k}/k clauses. The lopsided Loca Lemma shows that our result is asymptotically best possible. The determination of this extremal function is particularly important as it represents the value where the kSAT problem exhibits its complexity hardness jump: from having every instance being a YESinstance it becomes NPhard just by allowing each variable to occur in one more clause. We also consider the related extremal function l(k) which denotes the maximum number, such that every kCNF formula with each clause containing k distinct literals and each clause having a common variable with at most l(k) other clauses, is satisfiable. We establish that l(k) = (1/e + o(1))2^{k} The SATformulas are constructed via special binary trees. In order to construct the trees a continuous setting of the problem is defined, giving rise to a differential equation. The solution at 0 diverges, which in turn implies that the binary tree obtained from the discretization of this solution has the required properties. Joint work with Heidi Gebauer and Gabór Tardos. 
10.12.2010 

Yury Person (FU Berlin) 
Extremal Hypergraphs for Hamilton Cycles 
Abstract: We study sufficient conditions for various Hamilton cycles in kuniform hypergraphs and obtain both Turán and Diractype results. In particular, we show that the only extremal 3uniform hypergraph (for n moderately large) not containing a loose Hamilton cycle on n vertices consists of the complete hypergraph on n  1 vertices and an isolated vertex (thus answering a question of Woitas). More generally, we determine extremal hypergraphs for socalled ltight Hamilton cycles and we give first sufficient conditions on the minimum degree δ of type c(n choose k  1), with fixed c < 1 and n sufficiently large, that ensure the existence of Hamilton cycles. Joint work with Roman Glebov and Wilma Weps. 
03.12.2010 

Michael Krivelevich (Tel Aviv University) 
The Size Ramsey Number of a Directed Path 
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 qcoloring 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)}. A joint work with Ido BenEliezer (Tel Aviv U.) and Benny Sudakov (UCLA). 