Combinatorics Seminar 2011/2012 If
you are interested in talks of the previous years, go to Archive.
Abstracts
Michael Krivelevich, The Size Ramsey Number of a Directed Path Tibor Szabó, Gabór Tardos, The Oberwolfach Problems Tibor Szabó, The Local Lemma is tight for SAT II Dmitry Shabanov, The Problem of Erdös and Hajnal Concerning Colorings of Hypergraphs
and its Generalizations 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 graphs. 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 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. 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. 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 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. 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 Ziegler. 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 Szemeredi. 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. |