Mittagsseminar
Diskrete Mathematik 2009/10
AG
Prof. Tibor Szabó
|
Date |
Name |
Title |
|
16
October, 12:00 |
Tibor
Szabó, FU Berlin |
|
|
23
October, 12:00 |
Tomislav Doslic, University of Zagreb |
Computing the bipartite edge frustration of
some classes of graphs |
|
26
October, 10:15 |
Dominik
Scheder, ETH Zurich |
|
|
09
November, 10:15 |
Philipp
Zumstein, ETH Zurich |
|
|
20
November, 12:00 |
Roman
Glebov, FU Berlin |
|
|
26
November, 10:15 |
Angelika
Steger, ETH Zurich |
|
|
11
December, 14:15 |
Michael Krivelevich, Tel Aviv University |
|
|
6
January, 12:00 |
Wojciech Samotij, University of Illinois at
Urbana-Champaign |
|
|
7
January, 10:15 |
Anna
Huber, MPII Saarbrücken |
Performance and Robustness of Randomized
Rumor Spreading Protocols |
|
8
January, 12:00 |
Yury
Person, HU Berlin |
|
|
13
January, 12:00 |
Reto
Spöhel, ETH Zürich |
Upper bounds for asymmetric Ramsey properties of random graphs |
|
22
January, 10:00 |
Andrew Treglown, University of Birmingham |
|
|
23
February, 11:15 |
Heidi
Gebauer, ETH Zurich |
|
|
3
March, 12:00 |
Gabor Tardos, Simon Fraser University and Renyi
Institute |
|
|
12
March, 12:00 |
Wilma
Weps, FU Berlin |
|
|
18
March, 12.00 |
Anita
Liebeanu, Cambridge University |
|
|
21
April, 11:15 |
Tibor
Szabó, FU Berlin |
|
|
28
April, 11:00 |
Oleg Pikhurko, Carnegie Mellon University |
|
|
5
Mai, 11:00 |
Yury
Person, HU Berlin
|
|
|
12
Mai, 11:00 |
Roman
Glebov, FU Berlin |
|
|
19
Mai, 11:00 |
Roman
Glebov, FU Berlin |
|
|
2
June, 11:00 |
Gábor
Mészáros, HU Berlin |
|
|
11
June, 11:00 |
Balazs Szegedy, University of Toronto |
|
|
16
June, 11:00 |
Wilma
Weps, FU Berlin |
|
|
25
June, 11:00 |
Anusch
Taraz, TU Munich |
|
|
9 July,
11:00 |
Gábor
Mészáros, HU Berlin |
Abstracts
Tibor Szabó, Minimum degree of minimal ramsey graphs
A graph G is called H-Ramsey if any two-coloring of
the edges of G contains a monochromatic copy of H.
An H-Ramsey graph is called H-minimal if no proper subgraph of it is H-Ramsey.
We investigate the inimum degree of H-minimal graphs, a problem initiated
by Burr, Erdös, and Lovász.
We determine the smallest possible minimum degree of H-minimal graphs for
numerous bipartite graphs H,
including bi-regular bipartite graphs and forests.
We also make initial progress for graphs of larger chromatic number.
Tomislav Doslic, Computing
the bipartite edge frustration of some classes of graphs
The bipartite edge frustration of a graph is defined
as the smallest number of edges
that have to be deleted from the graph in order to obtain a bipartite spanning
subgraph.
The quantity is, in general, difficult to compute;
however it can be efficiently computed for certain classes of graphs.
I will speak about computing the bipartite edge frustration of some planar
graphs, in particular fullerenes,
and of some composite graphs.
Dominik Scheder, Deterministic Local Search for 3-SAT
In an attempt to derandomize
Schoening's famous algorithm for k-SAT,
Dantsin et al. proposed a deterministic k-SAT algorithm based on
covering codes and deterministic local search.
The deterministic local search procedure was subsequently improved by
several authors. I will present the main ideas behind the algorithm and
the latest improvements, one of them by myself.
At the heart of my improvement is the idea that recursive search-trees
can sometimes be Copy-Pasted to save time.
Philipp Zumstein, Polychromatic
Colorings of Plane Graphs
A vertex k-coloring of a plane graph G is called
polychromatic if in
every face of G all k colors appear. Let p(G) be the maximum number k
for which there is a polychromatic k-coloring.
For a plane graph G, let g(G) denote the length of the shortest face in
G. We show p(G) >= (3g(G)-5)/4 for every plane graph G and on the other
hand for each g we construct a plane graph H with g(H) = g and
p(H) <= (3g+1)/4.
Furthermore, we show that the problem of determining whether a plane graph
admits a vertex coloring by 3 colors in which all colors appear in every
face is NP-complete, even for graphs in which all faces are of length 3 or
4 only.
The investigation of this problem is motivated by its connection to a
variant of the art gallery problem in computational geometry.
Joint work with Noga Alon, Robert Berke, Kevin Buchin, Maike Buchin,
Peter Csorba, Saswata Shannigrahi, and Bettina Speckmann.
Roman Glebov, Extremal Graphs for Clique-Paths
In this talk, we deal with a
Tur\'an-type problem: given a
positive integer $n$ and a forbidden graph $H$, how many edges can
there be in a graph on $n$ vertices without a subgraph $H$? And
how does a graph look like, if it has this extremal edge number?
The forbidden graph in this talk is a clique-path, that is an
$k$-path, where each edge is blown up to an $r$-clique, $r \geq
3$. We determine both the extremal number and the extremal graph
for sufficiently large $n$.
Angelika Steger, A
deletion method for local subgraph counts
For a given graph H let X denote the random variable that counts the
number of copies of H in a random graph. For subgraph counts one
can use Janson’s inequality to obtain upper bounds on the probability
that X is smaller than its expectation. For the corresponding upper tail,
however, such bounds are not obtained easily and are known to not hold
with similarly small probabilities.
In this talk we thus consider the following variation of the problem:
we want to find a subgraph that on the one hand still contains at roughly
E[X] many H-subgraphs, and on the other hand has the property that every
vertex (and more generally every small subset of vertices) is contained in
‘not too many‘ H-subgraphs.
This is joint work with Reto Spöhel and Lutz Warnke.
Michael Krivelevich, Intelligence vs Randomness: the power of choices
Consider the following
very standard experiment: n balls are thrown
independently at random each into n bins (if you are practically inclined,
think about distributing n jobs at random between n machines). It is quite
easy to see that the maximum load over all bins will be almost surely
about ln n/lnln n. If however each ball is allowed to choose between two
randomly drawn bins, the typical maximum bin load drops dramatically to
about lnln n, as shown in a seminal paper of Azar, Broder, Karlin and
Upfal from 1994 - an exponential improvement!
The above described result is just one manifestation of a recently widely
studied phenomenon, where a limited manipulation of the otherwise truly
random input is capable to advance significantly various goals. In this
talk I will describe results of this type, mainly focusing on the so
called controlled random graph processes, where at each stage an algorithm
is presented with a collection of randomly drawn edges and is allowed to
manipulate this collection in a certain predefined way. Models to be
defined and discussed include the Achlioptas process and Ramsey-type games
on random graphs.
Wojciech Samotij, Counting graphs without a
fixed complete bipartite subgraph
A graph is called H-free if it contains no copy of H.
Denote by f_n(H) the
number of (labeled) H-free graphs on n vertices. Since every subgraph of
an H-free graph is also H-free, it immediately follows that
f_n(H) \geq 2^{\ex(n,H)}. Erdos conjectured that, provided H contains a
cycle, this trivial lower bound is in fact tight, i.e.
f_n(H) = 2^{(1+o(1))\ex(n,H)}.
The conjecture was resolved in the affirmative for graphs with chromatic
number at least 3 by Erdos, Frankl and Rodl (1986), but the case when H is
bipartite remains wide open. We will give an overview of the known results
in case \chi(H)=2 and present our recent contributions to the study of
H-free graphs.
This is joint work with Jozsef Balogh (University of
California, San Diego).
Anna Huber, Performance
and Robustness of Randomized Rumor Spreading Protocols
Randomized rumor spreading is a classical protocol to disseminate
information in a network. Initially, one vertex of a finite, undirected
and connected graph has some piece of information (``rumor''). In each
round, every one of the informed vertices chooses one of its neighbors
uniformly and independently at random and informs it. At SODA 2008, a
quasirandom version of this protocol was proposed. There, each vertex has
a cyclic list of its neighbors. Once a vertex has been informed, it
chooses uniformly at random only one neighbor. In the following round, it
informs this neighbor and in each subsequent round it informs the next
neighbor from its list.
I will talk about recent results on the performance and robustness of
these two protocols, in particular about the runtime on random graphs and
about the robustness on the complete graph.
Yury Person, Minimum
H-decompositions of graphs
Let $\phi_H(G)$ be the minimum number of graphs needed to partition the edge
set of $G$ into edges ($K_2$) and edge-disjoint copies of $H$. The problem
is what graph $G$ on $n$ vertices maximizes $\phi_H(G)$?
Bollob\'as showed that for $H=K_r, r\ge 3$ the only maximizer is the
Tur\'an graph. Pikhurko and Sousa extended his result for general $H$ with
$\chi(H)=r\ge 3$ and proved an upper bound being $t_{r-1}(n)+o(n^2)$, where
$t_{r-1}(n)$ is the number of edges in $(r-1)$-partite Tur\'an graph on $n$
vertices. They also conjectured that $\phi_H(G)=\ex(n,H)$. In the talk, we
verify their conjecture for odd cycles, and show that the only graph
maximizing $\phi_{C_{2l+1}}(G)$ is the Tur\'an graph, for large $n$. Joint
work with Lale \"Ozkahya.
Reto Spöhel, Upper
bounds for asymmetric Ramsey properties of random graphs
Consider the following problem: Is there a coloring of the
edges of the random graph $G_{n,p}$ with two colors such that there is no
monochromatic copy of some fixed graph $F$? A celebrated result by Rödl
and Rucinski (1995) states a general threshold function $p_0(F,n)$ for the
existence of such a coloring. Kohayakawa and Kreuter (1997) conjectured
a general threshold function for the asymmetric case (where different
graphs $F_1$ and $F_2$ are forbidden in the two colors), and verified this
conjecture for the case where both graphs are cycles.
Implicit in their work is the following more general statement: The
conjectured threshold function is an upper bound on the actual threshold
provided that i) the two graphs satisfy some balancedness condition, and
ii) the so-called K{\L}R-Conjecture is true for the sparser of the two
graphs. We present a new upper bound proof that does not depend on the
K{\L}R-Conjecture. Together with earlier lower bound results
[Marciniszyn, Skokan, S., Steger (2006)], this yields in particular a full
proof of the Kohayakawa-Kreuter conjecture for the case where both graphs
are cliques.
Andrew Treglown, Hamilton
cycles in directed graphs
Since it is unlikely that there is a characterization of all those graphs
which contain a Hamilton cycle it is natural to ask for sufficient
conditions which ensure Hamiltonicity. One of the most general of these is
Chv\'atal's theorem that characterizes all those degree sequences which
ensure the existence of a Hamilton cycle in a graph: Suppose that the
degrees of a graph $G$ are $d_1\leq \dots \leq d_n$. If $n\geq 3$ and
$d_i\geq i+1$ or $d_{n-i}\geq n-i$ for all $i<n/2$ then $G$ is
Hamiltonian. This condition on the degree sequence is best possible in the
sense that for any degree sequence violating this condition there is a
corresponding graph with no Hamilton cycle.
Nash-Williams conjectured a digraph analogue of Chv\'atal's theorem quite
soon after the latter was proved. In the first part of the talk I will
discuss an approximate version of this conjecture.
A Hamilton decomposition of a graph or digraph $G$ is a set of
edge-disjoint Hamilton cycles which together cover all the edges of $G$. A
conjecture of Kelly from 1968 states that every regular tournament has a
Hamilton decomposition. We recently proved the following approximate
version of Kelly's conjecture: Every regular tournament on $n$
vertices contains $(1/2-o(1))n$ edge-disjoint Hamilton cycles. I will
discuss some of our techniques as well as some related open problems in
the area. This is joint work with Daniela K\"uhn and Deryk Osthus.
Heidi Gebauer, Game
Theoretic Ramsey Numbers
The Ramsey Number, R(k), is defined as the minimum N such that every
2-coloring of the edges of K_N (the complete graph on N vertices) yields a
monochromatic k-clique. For 60 years it is known that 2^(k/2) < R(k) <
4^k, and it is a widely studied open problem to find significantly better
bounds. In this talk we consider a game theoretic variant of the Ramsey
number: Two players, called Maker and Breaker, alternately claim an edge
of K_N. Maker's goal is to completely occupy a K_k and Breaker's goal is
to prevent this. The game theoretic Ramsey Number R'(k) is defined as the
minimum N such that Maker has a strategy to build a K_{k} in the game on
K_N. In contrast to ordinary Ramsey numbers, R'(k) has been determined
precisely -- a result of Beck. We will sketch a new, weaker result about
R'(k) and use it to solve some related open problems.
Gabor Tardos, Conflict
free coloring of neighborhoods in graphs
A (not necessarily proper) vertex coloring of a graph is called
conflict-free (with respect to the neighborhoods) if the neighborhood N(x)
of any vertex x contains a vertex whose color is not repeated in N(x).
We consider how many colors are needed in the worst case for conflict-free
coloring of an n vertex graph. Surprisingly the answer depends very
strongly on whether one considers the neighborhood N(x)to contain or
exclude x itself.
The results are joint with Janos Pach.
Wilma Weps, Nonrepetitive
colorings of graphs
Nonrepetitive coloring of graphs is a graph theoretic variant of the
nonrepetitive sequences of Thue. A (in)finite sequence is called
k-nonrepetitive (k >= 2) if it contains no k-repetition, i.e. a block B
of the form B = CC...C (k-times) with C being a nonempty block. A vertex
coloring f of a graph G is called nonrepetitive if each path P in G has a
2-nonrepetitive sequence f(P) of colors.
Defining the Thue number of a graph to be the smallest number of colors
needed for such a coloring, one is interested in estimating this graph
invariant.
I will present a theorem by Alon et al. proving the Thue number is
bounded by the maximum degree of a graph; furthermore, a theorem by
Kündgen and Pelsmajer showing the Thue number is bounded by the
treewidth of a graph from above.
However, for most classes of graphs the exact value of the Thue number
remains unknown.
Anita Liebeanu, Balog-Szemerédi-Gowers
Theorem
The Balog-Szemerédi-Gowers theorem is a result in the field of additive
combinatorics and gives a relationship between the sizes of sum sets and
partial sum sets. Surprisingly, the proof is purely graph theoretical
and relies on a statement about paths of length 3 in a bipartite graph.
It is the object of this talk to develop this relationship as well as
giving sketches of the proofs of the corresponding statements in graph
theory.
I will assume only basic definitions of graph theory and no previous
knowledge about additive combinatorics.
Tibor Szabo, A
combinatorial model for the diameter of a polyhedra
The Hirsch Conjecture states that the diameter of a
$d$-dimensional polytope with $n$ facets is at most $n-d$. The best
general upper bound due to Kalai and Kleitman is $n^{1+\log d}$. For
constant dimension Larman showed that the diameter is linear in $n$.
Recently, Eisenbrand, Hähnle, Razborov, and Rothvoß introduced a
combinatorial model for the problem which
1) admits both of the upper bound proofs,
2) gives rise to a superlinear lower bound.
The lower bound is proved using the Lovasz Local Lemma.
In the talk we present this paper.
Oleg Pikhurko, An
analytic approach to stability
This is an attempt to understand how the recently developed
theory of graph limits may apply to finite problem of extremal graph
theory. We formulate the notion of a stable problem (meaning, roughly
speaking, that almost extremal graphs have structure close to that of an
extremal graph) and give an equivalent characterization in terms of graph
limits. As an application, we present a new proof of the Erdös-Simonovits
stability theorem.
Yury Person, A
conjecture of Erdös on graph Ramsey numbers
For a given graph G, let r(G) be the minimum number n such that any
two-coloring of the edges of the complete graph
K_n on n vertices yields a monochromatic copy of G. For example it is
known that r(K_k) is at least 2^{k/2} and at most 2^{2k}
and despite efforts of many researchers the constant factors in the
exponents remain the same for more than 60 years!
For a graph G with m edges and no isolated vertices Erdös conjectured
that r(G) < 2^{C\sqrt{m}} (this would be then best
possible up to a constant factor in view of the above mentioned bounds
for r(K_k)). Very recently, Benny Sudakov proved this conjecture.
In my talk I will present Sudakov's proof and discuss some related
results and propblems in the area.
Roman Glebov, On-line
Ramsey Numbers I
In Ramsey theory, we mostly look at the number r(t) denoting the minimum
number of vertices sich that a two-coloring of the edges of the clique on
r(t) many vertices necessarily produces a monochromatic t-subclique (we
also say an r(t)-clique "arrows" a t-clique). The size Ramsey number
r'(t)
is the smallest number of edges such that there exists a graph with r'(t)
edges arrowing an r(t)-clique.
In my two talks I present the on-line version of this problem according to
a resent paper by David Conlon. In a two-players-game, Builder draws edges
one-by-one, and Painter colors them as each appears. Builder's aim is to
force Painter to draw a monochromatic t-clique. The minimum number of
edges which Builder must draw is the on-line Ramsey number r''(t). The
main result presented in the first talk is the fact that for in finitely
many values of t, r''(t) is exponentially smaller than r'(t).
Roman Glebov, On-line
Ramsey Numbers II
In Ramsey theory, we mostly look at the number r(t) denoting the minimum
number of vertices sich that a two-coloring of the edges of the clique on
r(t) many vertices necessarily produces a monochromatic t-subclique (we
also say an r(t)-clique "arrows" a t-clique). The size Ramsey number
r'(t)
is the smallest number of edges such that there exists a graph with r'(t)
edges arrowing an r(t)-clique.
In my two talks I present the on-line version of this problem according to
a resent paper by David Conlon. In a two-players-game, Builder draws edges
one-by-one, and Painter colors them as each appears. Builder's aim is to
force Painter to draw a monochromatic t-clique.
In my second talk on the on-line Ramsey numbers, I present
a specific upper bound for r''(t) of order 4^{t-c(log^2(t))/(loglog(t))}.
Gábor Mészáros, Path Size Ramsey
Numbers
The size Ramsey number $\hat{r}(G)$ of a graph $G$ is the smallest
integer $\hat{r}$ such that there is a graph $F$ of $\hat{r}$ edges
with the property that any two-coloring of the edges of $G$ yields a
monochromatic copy of G. An obvious upper bound is known for the
size Ramsey number of an arbitrary graph G,namely $\hat{r}(G)\leq
\binom{r(G)}{2}$ where $r(G)$ denotes the Ramsey number of G.
For paths Erdős offered 100\$ for a proof or disproof of the
following conjectures:
$\frac{\hat{P_n}}{n}\rightarrow \infty$
$\frac{\hat{P_n}}{n^2}\rightarrow 0$
In 1983 Beck proved that for every sufficiently large value of n
$\hat{r(P_n)<900\cdot n}$, which result answered Erdős's question.
In my talk I will present Beck's proof and discuss some related
results in the area, including some interesting counterexamples
which tell us that Beck's result is not necessarily true for general
trees.
Balazs Szegedy, Limits
of discrete structures (recent directions)
This talk is a status report on a recently developing subject in
the frame of which big finite structures are viewed as approximations of
infinite analytic structures. This framework enables one to use differential
calculus, measure theory, topology and other infinite tools to analyze
finite structures.
Wilma Weps, On
Size Ramsey Number of Graphs with Bounded Maximum Degree
The size Ramsey number $\hat{r}(G)$ of a graph $G$ is the smallest
number of integers $\hat{r}$ such that there exists a graph $F$ with
$\hat{r}$ edges for which every red-blue-edge-coloring
contains a monochromatic copy of $G$.
Josef Beck raised the question whether for a graph $G$ with bounded
maximum degree $d$ there exists a constant $c(d)$ depending only on the
maximum degree such that $\hat{r}(G) < c(d)*n$, with
$n$ the number of vertices of $G$.
It has shown to be true that such a constant exists if $G$ is a cycle or a
tree.
In my talk I will present a counterexample by Rödl and Szemeredi which
shows that the statement above already fails if $d=3$.
Anusch Taraz, On
co-prime labellings of trees
A conjecture by Entringer from around 1980 states that the vertices of
every n-vertex tree can be labelled with numbers 1 up to n in such a way
that adjacent vertices get co-prime labels. In joint work with P.E. Haxell
and O. Pikhurko we recently managed to prove this conjecture for
sufficiently large n. I will discuss the proof in this talk.
Gábor Mészáros, Road
Coloring Problem
The road coloring problem deals with the
question whether there exists
an edge-coloring of a network such that by using special instructions,
one can reach or locate an object or destination from any other point within
the network.
Precisely, if you have a directed graph G with regular out-degree k, the main
question is,
whether you can color the edges such a way, that:
i) all k edges leaving any vertex have distinct colors and
ii) there is a suitable sequence w of colors, such that no matter which vertex
we choose
as start-point we get the same end-point, reading the word w label to label
and choosing the suitable edge (according to w), on which we can travel to the
next vertex.
It was first conjectured in 1970 by Weiss and Adler, that one can always find
an appropriate coloring with a suitable word, if the digraph is strongly
connected and aperiodic,
that is, there is no integer k > 1 that divides the length of every cycle of
the graph.
In 2007 Trahtman proved the conjecture (now it is called Road coloring
theorem).
In my talk I will present a partial result proved by Kari (2002), which says
that
the theorem is true if the graph is eulerian and regular, that is, all vertices
have in and outdegree k.