Combinatorics Seminar 2011/2012

If you are interested in talks of the previous years, go to Archive.







December 3rd, 2010

Michael Krivelevich
Tel Aviv University

The Size Ramsey Number of a Directed Path

December 10th, 2010

Yury Person
Freie Universität Berlin

Extremal Hypergraphs for Hamilton Cycles

December 17th, 2010

Tibor Szabó
Freie Universität Berlin

The Local Lemma is tight for SAT

January 14th, 2011

Tibor Szabó
Freie Universität Berlin

Gábor Tardos
Rényi Institute of Mathematics

The Oberwolfach Problems

January 21st, 2011

Tibor Szabó
Freie Universität Berlin

The Local Lemma is tight for SAT II

January 28th, 2011

Dmitry Shabanov
Moscow State University

The Problem of Erdös and Hajnal Concerning Colorings of Hypergraphs and its Generalizations

February 16th, 2011

Oliver Friedman
LMU München

On Exponential Lower Bounds 
for Solving Infinitary Payoff Games
and Linear Programs: Part II

February 23rd, 2011

Katherine Edwards

McGill University

Packing T-joins in Planar Graphs

February 24th, 2011

Fiona Skerman
Australian National University
Row and column sums of random 0-1 matrices

May 4th, 2011

Dennis Clemens
FU Berlin
The uniqueness conjecture of Markoff numbers
and equivalent problems: Part I

May 12th, 2011

Dennis Clemens
FU Berlin
The uniqueness conjecture of Markoff numbers
and equivalent problems: Part II

May 13th, 2011

Dan Spielman
Yale University
On some problems that have been bugging me

May 20th, 2011

Timothy Gowers
University of Cambridge
A combinatorial proof of the density  
Hales-Jewett theorem

June 9th, 2011

Endre Szemerédi

Rényi Institute of Mathematics

Long Arithmetic Progression in Sumsets

June 15th, 2011

Anita Liebenau
Freie Universität Berlin

A survey on the 'Cops-and-robbers problem'

June 22nd, 2011

Hanno Lefmann

TU Chemnitz
Edge Colorings of Graphs and Fixed 
Forbidden Monochromatic Subgraphs

June 29th, 2011

Benny Sudakov
Nonnegative k-sums, fractional covers, 
and probability of small deviations

July 6th, 2011

Uri Zwick
Tel Aviv University 

All-Pairs Shortest Paths in O(n^2) Expected


July 13th, 2011

Kevin Milans
University of South Carolina

August 23rd, 2011

Benjamin Matschke
FU Berlin

Equivariant topology methods

and the colored Tverberg problem

September 7th, 2011

Roman Glebov
FU Berlin

Rainbow matchings in hypergraphs

September 30th, 2011

Jan Hladky

Warwick Mathematics Institute

Loebl-Komlos-Sos Conjecture and

embedding trees in sparse graphs

October 19th, 2011

Tibor Szabó 

    Freie Universität Berlin

Sharp threshold for bounded degree

spanning trees with many leaves or a long

bare path

October 28th, 2011

Christoph Koch

TU München

On Kuratowski's Theorem

and the Kelmans-Seymour conjecture

November 4th, 2011

Dieter Jungnickel

Universität Augsburg

November 9th, 2011

Valentina Pepe

Ghent University

November 16th, 2011

Julia Wolf

École Polytechnique, Paris




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

Yury Person, Extremal Hypergraphs for Hamilton Cycles
We study sufficient conditions for various Hamilton cycles in k-uniform hypergraphs and obtain both Turan- and Dirac-type results. In particular, we show that the only extremal 3-uniform 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 so-called l-tight Hamilton cycles and we give first sufficient conditions on the minimum degree \delta of type c\binom{n}{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.

Tibor Szabó, The Local Lemma is tight for SAT
We construct unsatisfiable k-CNF 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 k-SAT problem exhibits its complexity hardness jump: from having every instance being a YES-instance it becomes NP-hard 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 k-CNF 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 SAT-formulas 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 Gabor Tardos.


Tibor Szabó, Gabór Tardos, The Oberwolfach Problems
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.


Tibor Szabó, The Local Lemma is tight for SAT II
I will give a construction of unsatisfiable $k$-SAT 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 Gabor Tardos.


Dmitry Shabanov, The Problem of Erdös and Hajnal Concerning Colorings of Hypergraphs and its Generalizations
The talk is devoted to the classical exremal combinatorial problem that was stated by P.Erdös and A.Hajnal in the 60-s. The task is to find the value m(n,r) equal to the minimum number of edges in an n-uniform non-r-colorable 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ös-Hajnal problem, present some new results and pay special attention to the probabilistic methods, by which these results have been obtained.


Oliver Friedman, On Exponential Lower Bounds for Solving Infinitary Payoff Games

and Linear Programs: Part II

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 so-called 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.


Katherine Edwards, Packing T-joins in Planar Graphs

Let G be a graph and T an even sized subset of its vertices. A T-join

is a subgraph of G whose odd-degree vertices are precisely those in T,

and a T-cut is a cut \delta(S) where S contains an odd number of

vertices of T. It has been conjectured by Guenin that if all T-cuts of

G have the same parity and the size of every T-cut is at least k, then

G contains k edge-disjoint T-joins. We discuss some recent progress on

this conjecture and related results.


Fiona Skerman, Row and column sums of random 0-1 matrices

Construct a random $m \times 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

$\textbf{s} = (s_1 , \ldots , s_m )$ and column sums $\textbf{t} = (t_1

, \ldots , t_n )$. Clearly $\textbf{s}$ and $\textbf{t}$ have the same

sum, but otherwise their dependencies are complicated. We prove that

under certain conditions the distribution of $(\textbf{s}, \textbf{t})$

is accurately modelled by $(S_1 , \ldots , S_m , T_1 , \ldots, 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 , \ldots , S_m , T_1 , \ldots ,

T_n$ are independent apart from satisfying

$\sum_{j=1}^m S_j = \sum_{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 $\textbf{s}$ when $\textbf{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


Joint work with Brendan McKay


Christian Reiher, The clique density problem

It is well known that by a theorem of Turán every graph on n vertices

possessing more than (r−2)n^2/(2r-2) edges has to contain a clique

of size r, where r > 3 denotes some integer.

Given that result, it is natural to wonder what one can say about the

number of r–cliques that have to be present in a graph on n vertices

with at least \gamma·n^2 edges, where \gamma > (r−2)/(2r−2) denotes

some real parameter.

In awareness of the structure of the graph that is extremal for Turán’s

original problem, it is quite tempting to suggest that the answer is

provided by first choosing some appropriate integer s > r − 1 depending

on \gamma alone and then constructing a complete (s+1)–partite graph

all of whose vertex classes except for one possibly smaller one are of

equal size. This gives a number of r–cliques that is proportional to nr and

it is an amazingly difficult problem to decide whether the factor of

proportionality thus obtained is indeed (asymptotically) best possible.

This question has first been asked by Lovász and Simonovits in the 1970s,

and has remained widely open until very recently when Razborov

introduced new analytical ideas and solved the case r = 3. Shortly

afterwards, Nikiforov solved the case r = 4. In the talk, we will present

the recent solution to this clique density problem, and discuss some

related ideas of Lovász and Razborov concerning graph limits.


Dennis Clemens, The uniqueness conjecture of Markoff numbers

and equivalent problems

In 1879/80 Andrei A. Markoff studied the minima of indefinite quadratic

forms and found an amazing relationship to the Diophantine equation

+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.

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



Endre Szemerédi, Long Arithmetic Progression in Sumsets

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)


Anita Liebenau, A survey on the 'Cops-and-robbers problem'

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


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


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.

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).


Hanno Lefmann, Edge Colorings of Graphs

and Fixed Forbidden Monochromatic Subgraphs

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_{\ell}$

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\'an graph for $F$, while for $r\geq 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.


Benny Sudakov, Nonnegative k-sums, fractional covers, and probability of small deviations

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 \binom{n-1}{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 \geq 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


Uri Zwick, All-Pairs Shortest Paths in O(n^2) Expected Time

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^2).

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^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


Benjamin Matschke, Equivariant topology methods and the colored Tverberg problem

The first part of this talk will be a quick survey on

equivariant topology methods and how to use them in discrete geometry.

The second part is about a particular application, the colored

Tverberg problem, which is joint work with Pavle Blagojević and Günter



Roman Glebov, Rainbow matchings in hypergraphs

We investigate the following problem: given a (large) integer r and a (sufficiently large)

integer t, we are presented an r-uniform r-partite multihypergraph that consists of f

matchings of size t. What is the extremal number f=f(t,r), such that we know that there

exists a t-matching with every hyperedge coming from a different matching? We present

an upper bound of order t^r, improving a previous bound of Alon. We also present an

observation leading to the intuition that the „extremal“ examples live on a small number

of vertices.

The aim of the talk is to equate our knowledge in the problem and to motivate further

joint research in this and closely related problems.


Joint work in progres with Benny Sudakov, Tibor Szabó, Yury Person and Anita Liebenau.


Jan Hladky, Loebl-Komlos-Sos Conjecture and embedding trees in sparse graphs

We prove an approximate version of the Loebl-Komlos-Sos Conjecture

which asserts that if half of the vertices of a graph G have degrees

at least k then G contains each tree T of order k+1 as a subgraph.


The proof of our result follows a strategy common to approaches which

employ the Szemeredi Regularity Lemma: the graph G is

decomposed, a suitable combinatorial structure inside the

decomposition is found, and then the tree T is embedded into G using

this structure. However the decomposition given by the Regularity

Lemma is not of help when G sparse. To surmount this shortcoming we

use a general decomposition technique (a variant of which was

introduced by Ajtai, Komlos, Simonovits and Szemeredi to resolve to

Erdos-Sos conjecture) which applies also to sparse graphs: each graph

can be decomposed into vertices of huge degree, regular pairs (in the

sense of the Regularity Lemma), and an expander-like part.


Joint work with Janos Komlos, Diana Piguet, Miki Simonovits, and Endre



Tibor Szabó, Sharp threshold for bounded degree spanning trees with many leaves or a long bare path

We show that any given n-vertex tree with bounded maximum degree and linearly many leaves is contained in the binomial random graph G(n,p) asymptotically almost surely for some p=(1+o(1))log n/n. Furthermore we also show that G(n,p) contains asymptotically almost surely every bounded degree spanning tree T that has a path of linear length whose vertices have degree two in T. This represents joint work with Dan Hefetz and Michael Krivelevich.


Christoph Koch, On Kuratowski's Theorem and the Kelmans-Seymour conjecture

Kuratowski's well-known theorem gives a precise characterization of

planar graphs - there are exactly two types of forbidden subgraphs in

planar graphs: subdivisions of $K_{3,3}$ and subdivisions of $K_5$.

Thus, a natural question to arise is the following: Are there classes of

graphs such that we need only check for one type of these subdivisions

in order to determine planarity? In the past decades there have been

many results of that kind, but still some problems remain unsolved. One

of them is the Kelmans-Seymour conjecture: Does every $5$-connected

non-planar graph contain a subdivided $K_5$?


This talk will illustrate two main approaches towards this conjecture.

In particular, there have been some partial results by various people

within the last year.






Mittagsseminar - Archive

·         Mittagseminar 2009 / 2010