Humboldt University Berlin, 20-21 June 2008
Schedule:
Schedule as pdf-documentFriday, 20 June 2008 |
||
| 14:00 | Opening and greetings | |
| 14:15 | Jeong Han Kim | Optimal Query Complexity Bounds for Finding Graphs |
| 15:00 | Florian Pfender | A Turan type theorem for multipartite graphs |
| 15:30 | Oleg Pikhurko | Game chromatic index of graphs with given restrictions on degrees |
| 16:00 | Break / PhD defence Stefan Kirchner | Untere Schranken für Steinerbaumalgorithmen und die Konstruktion von Bicliquen in dichten Graphen |
Saturday, 21 June 2008 |
||
| 8:45 | Coffee | |
| 9:00 | Anand Srivastav | Low-Discrepancy Colorings for Arithmetic Progressions |
| 9:30 | Bernd Kreuter | Patterns and Structures in real markets |
| 10:00 | Miroslawa Janczak | On a problem of Hilliker and Straus |
| 10:30 | Coffee | |
| 11:00 | Manuel Bodirsky | The Product Ramsey Theorem in Constraint Satisfaction Complexity |
| 11:30 | Julia Böttcher | (Not) separating between sublinear and linear bandwidth and treewidth |
| 12:00 | Wojciech Wawrzyniak | Distributed packing in planar graphs |
| 12:30 | Lunch | |
| 14:15 | Coffee | |
| 14:30 | Krzysztof Krzywdzinski | Distributed constant time algorithm for finding PTAS-approximation of Minimum Spanning Tree in Unit Disc Graphs |
| 15:00 | Mariano Zelke | Weighted Matching in Streaming Graphs |
| 15:30 | Taral Seierstad | The differential equations method |
| 16:00 | Coffee | |
| 16:15 | Vojtech Rödl | Folkman and Ramsey Numbers |
| 16:45 | Anusch Taraz / Mihyun Kang | Mathematical history of the Berlin-Poznan seminar |
| 17:45 | Closeing | |
All lectures will be held in
in room 1.306Erwin Schrödinger-Zentrum, HU Berlin Rudower Chaussee 26, 12489 Berlin
Abstracts
Manuel Bodirsky, Ecole Polytechnique
The Product Ramsey Theorem in Constraint Satisfaction Complexity
-
In this talk, I show how the product Ramsey theorem
can be used jointly with tools from universal algebra
to classify the complexity of a large class of computational problems
in temporal reasoning. I will also discuss open problems
both in constraint satisfaction and Ramsey theory.
Julia Böttcher, TU München
(Not) separating between sublinear and linear bandwidth and treewidth
-
Bandwidth and treewidth are well studied graph parameters. While lots of research is dedicated to determining these parameters rather precisely for certain graphs or to graph classes where they are constants, in this talk we will be mainly interested in distinguishing between graph classes where the bandwidth/treewidth is sublinear in the number of vertices and such where these parameters are linear.
The star shows that in general even trees (i.e. graphs of treewidth 1) can have linear bandwidth. Chung proved that trees with bounded maximum degree however have sublinear bandwidth. This raises the question wether such a result remains true for bounded-degree graphs of bigger treewidth. We answer this question in the affirmative. More generally, we prove that for any hereditary class of bounded-degree graphs the concepts of sublinear bandwidth, sublinear treewidth, the absence of big expanders as subgraphs, and the existence of small separators are equivalent.
This result implies that planar graphs with bounded maximum degree have sublinear bandwidth. As a consequence we can infer the following embedding result. For each gamma>0 every n-vertex graph (for n sufficiently large) with minimum degree (gamma+3/4)n contains a copy of every bounded-degree planar graph on n vertices.
Joint work with Klaas Pruessmann, Anusch Taraz, Andreas Würfl.
Miroslawa Janczak, Adam Mickiewicz University Poznan
On a problem of Hilliker and Straus
-
For a prime $p$ and a vector $\ha=(\alpha_1,\dots,\alpha_k)\in \Z_p^k$
let $f\left(\ha,p\right)$ be the largest $n$ such that in each set
$A\subseteq\Z_{p}$ of $n$ elements one can find $x$ which has a
unique representation in the form $x=\a_{1}a_1+\dots
+\a_{k}a_k,~a_i\in A$. Hilliker and Straus~\cite{hs} bounded
$f\left(\ha,p\right)$ from below by an expression which contained
the $L_1$-norm of $\ha$ and asked if there exists a positive
constant $c\left(k\right)$ so that
$f\left(\ha,p\right)>c\left(k\right)\log p$. In this note we answer
their question in the affirmative and show that, for large $k$, one
can take $c(k)=O(1/k\log (2k)) $.
We also give a lower bound for
the size of a set $A\subseteq \Z_{p}$ such that every element
of $A+A$ has at least $K$ representations in the form $a+a'$, $a, a'\in A$.
Jeong Han Kim, Yonsei University
Optimal Query Complexity Bounds for Finding Graphs
-
We consider the problem of finding an unknown graph by using two
types of queries with an additive property. Given a graph, an
additive query asks the number of edges in a set of vertices while
a cross-additive query asks the number of edges crossing between
two disjoint sets of vertices. The queries ask sum of weights for
the weighted graphs. These types of queries were partially
motivated in DNA shotgun sequencing and linkage discovery problem
of artificial intelligence.
For a given unknown weighted graph $G$ with $n$ vertices, $m$ edges, and a certain mild condition on weights, we prove that there exists a non-adaptive algorithm to find the edges of $G$ using $O\left(\frac{m\log{n}}{\log{m}}\right)$ queries of both types provided that $m \geq n^{\epsilon}$ for any constant $\epsilon> 0$. For a graph, it is shown that the same bound holds for all range of $m$.
This settles a conjecture of Grebinski for finding an unweighte graph using additive queries. We also consider the problem of finding the Fourier coefficients of a certain class of pseudo-Boolean functions. A similar coin weighing problem is also considered.
Stefan Kirchner, Humboldt-Universität zu Berlin
PhD thesis
-
My PhD thesis consists of two parts. The first part is concerned with lower bounds for approximating Steiner trees. The Steiner tree problem is to find a shortest subgraph that spans a given set of vertices in a graph and is a classical NP-hard problem. Several approximation algorithms exist, but for most algorithms only lower and upper bounds for the approximation ratio are known. For some of these algorithms we present instances which improve the lower bounds. When the problem is restricted to the class of graphs with k terminals, we also present a method which can be used to determine the approximation ratio of the Relative Greedy Algorithm with arbitrary precision.
The second part is about balanced bicliques, i.e. complete bipartite subgraphs with equal partition sizes. It has been known for a long time that every dense bipartite graph contains a balanced biclique of size O(log(n)), but whether and how such a biclique can be constructed in polynomial time is still unknown. Our contribution to this problem is a polynomial time algorithm which constructs a balanced biclique of size O(sqrt(log(n))) in sufficiently large and dense bipartite graphs.
Bernd Kreuter
Patterns and Structures in real markets
-
Patterns and Structures in real markets -- on data mining, multi agent
set-ups, the failure of classical probability theory, trading
strategies, and many unsolved problems
Krzysztof Krzywdzinski, Adam Mickiewicz University Poznan
Distributed constant time algorithm for finding PTAS-approximation of Minimum Spanning Tree in Unit Disc Graphs
-
The Unit Disc Graphs (UDG) is the most natural class of graphs to model wireless ad hoc networks (for example cell phon
es networks, wireless sensor networks etc.). The set of vertices of UDG is a set of points on the plane and two vertice
s of UDG, $v$ and $w$, are connected by an edge in UDG if and only if they are at the distance at most one in Euklidi
an norm ($\left\|v,w\right\| \leq 1$). From application point of view it means that the vertices (cell phones, sensors
etc.) are in their communication range. By the weight of an edge $(v,w)$ in UDG we mean the distance between $v$ and $w
$ on the plane. Moreover as the weight of a graph (of a subgraph of UDG as well) we define a sum of weights of its edge
s.
One of the most fundamental problems concerning Unit Disc Graphs is finding a Minimum (in terms of its weight) Spannin g Tree of the arbitrarily given Unit Disc Graph G ($MST(G)$). In my presentation I will introduce a new distributed alg orithm, which finds in $O(poly(D))$ synchronous rounds a subgraph $H$ of $G$, which is a good approximation of $MST(G)$ .
Namely I will prove, that given as an input parameter $D$ and a Unit Disc Graph $G$, the presented algorithm finds in $ O(poly(D))$ synchronous rounds, a subgraph $H$ of $G$ with four following properties:
$H$ contains one of the $MST(G)$;
weight of $H$ is $(1+O(1/D))$ approximation of the weight of $MST(G)$;
$H$ is planar;
if a shortest path between $v$ and $w$ in $G$ have weight $K$, then the shortest path between $v$ and $w$ in $H$ have weight $O(D)K$.
Florian Pfender, Universität Rostock
A Turan type theorem for multipartite graphs
-
Turan's Theorem states that every graph of a certain edge density
contains a complete graph K^k
and describes the unique extremal graphs. We give a similar Theorem
for l-partite graphs. For large
l, we find the minimal edge density d_k , such that every l-partite
graph whose parts have pairwise
edge density greater than d_k contains a K^k . It turns out that d-k =
(k-2)/(k-1) for large enough l,
refuting a conjecture by Bondy, Shen, Thomasse and Thomassen. We also
describe the structure of the extremal graphs.
Oleg Pikhurko, Carnegie Mellon University
Game chromatic index of graphs with given restrictions on degrees
-
Given a graph $G$ and an integer $k$, two players alternatively color the
edges of $G$ using $k$ colors so that adjacent edges get different colors.
The \emph{game chromatic index} $\chi'_g(G)$ is the minimum $k$ for which
the first player has a strategy that ensures that all edges of $G$ get
colored.
Lam, Shiu, and Xu and, independently, Bartnicki and Grytczuk asked whether there is a constant $C$ such that $\chi_g'(G)\le \Delta(G)+C$ for every graph $G$. We show that the answer is in the negative. Also, general upper bounds on $\chi'(G)$ in terms of $\Delta(G)$ and $v(G)$ will be discussed.
This is a joint work with Andrew Beveridge, Tom Bohman, and Alan Frieze.
Taral Seierstad, University of Oslo
The differential equations method
-
Wormald's differential equation method is often used to show that
parameters defined on random graph processes converge in probability to
the solutions of certain differential equations. We show that this
method, in many cases, can be extended to show that the parameters
converge to a multivariate normal distribution.
Anand Srivastav, Christian-Albrechts-Universität zu Kiel
Low-Discrepancy Colorings for Arithmetic Progressions
-
One of the celebrated theorems in
discrepancy theory says that the 2-color discrepancy of the hypergraph
of arithmetic progressions in the first $n$ integers is
$\Theta(n^{1/4})$ (lower bound by Roth (1964), upper bound
Matou\v{s}ek, Spencer (1994)). In this talk we
give an overview on the discrepancy problem for
different kind of arithmetic progressions, among
them sums and products, both in the natural numbers as well
as in $\mathbb{Z}_{p}$. In particular, we will prove
tight bounds for the $c$-color discrepancy function
for centered arithmetic progressions in $\mathbb{Z}_{p}$.
Here, due to the lack of translation-invariance
of the hypergraph Fourier analysis alone does not work,
and has to be combined with a new decomposition of such progressions.
Wojciech Wawrzyniak, Adam Mickiewicz University Poznan
Distributed packing in planar graphs
-
I'll give an efficient distributed algorithm that finds an almost optimal packing of a graph H in a planar graph G. The algorithm is deterministic and its running time is poly-logarithmic in the order of G.
Mariano Zelke, Humboldt University Berlin
Weighted Matching in Streaming Graphs
-
The Semi-Streaming Model forbids random access to the input and uses a working memory of restricted size. It was proposed by Muthukrishnan in 2003 and is appropriate when tackling massive graphs. For the problem of finding the maximum weighted matching, which is intractable in the Semi-Streaming Model, we will present the best known approximation algorithm.
Contact:
Dr. Mihyun KangPostal address Johann von Neumann-Haus Humboldt-Universität zu Berlin Institut für Informatik Rudower Chaussee 25 12489 Berlin
Tel. : (+49 30) 2093 3830 Fax : (+49 30) 2093 3191 e-mail : kang@informatik.hu-berlin.de
Deutsch